POJ 3686 The Windy's - c++编程基础

int d=inf;
for(int i=1;i<=m;i++)
{
if(!visity[i])
{
d = min(d,slack[i]);
}
}
for(int i=1;i<=n;i++)
{
if(visitx[i])
{
lx[i] -=d;
}
}
for(int i=1;i<=m;i++)
{
if(visity[i])
{
ly[i] +=d;
}else
{
slack[i] -=d;
}
}
}
}
int s=0;
for(int i=1;i<=m;i++)
{
if(linky[i])
{
int j=linky[i];
s+=w[j][i];
}
}
return -s;
}

/***************************************************************
> File Name: POJ3686.cpp
> Author: SDUT_GYX
> Mail: 2272902662@qq.com
> Created Time: 2013/6/4 0:16:38
**************************************************************/

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define N 3600
#define inf 0x7ffffff
using namespace std;
int lx[N],ly[N],slack[N],linky[N],w[N][N],n,m;
bool visitx[N],visity[N];
int main()
{
//freopen("data1.in","r",stdin);
int KM();
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
int x;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&x);
for(int k=1;k<=n;k++)
{
w[i][(j-1)*n + k] = -x*k;
}
}
}
m=n*m;
int res=KM();
printf("%.6lf\n",(double)res/n);
}
return 0;
}
bool find(int k)
{
visitx[k] = true;
for(int i=1;i<=m;i++)
{
if(visity[i])
{
continue;
}
int t=lx[k] + ly[i] - w[k][i];
if(t==0)
{
visity[i] = true;
if(!linky[i]||find(linky[i]))
{
linky[i] = k;
return true;
}
}else
{
slack[i]=min(slack[i],t);
}
}
return false;
}
int KM()
{
memset(ly,0,sizeof(ly));
memset(linky,0,sizeof(linky));
for(int i=1;i<=n;i++)
{
lx[i] = -inf;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
lx[i] = max(lx[i],w[i][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
slack[j] = inf;
}
while(1)
{
memset(visitx,false,sizeof(visitx));
memset(visity,false,sizeof(visity));
if(find(i))
{
break;
}
int d=inf;
for(int i=1;i<=m;i++)
{
if(!visity[i])
{
d = min(d,slack[i]);
}
}
for(int i=1;i<=n;i++)
{
if(visitx[i])
{
lx[i] -=d;
}
}
for(int i=1;i<=m;i++)
{
if(visity[i])
{
ly[i] +=d;
}else
{
slack[i] -=d;
}
}
}
}
int s=0;
for(int i=1;i<=m;i++)
{
if(linky[i])
{
int j=linky[i];
s+=w[j][i];
}
}
return -s;
}

POJ 3686 The Windy's (二)