#include <iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<climits>
using namespace std;
int g[505][505];
int dx[505],dy[505];
bool vx[505], vy[505];
int dis[505]; int n, x, y;
int res, minn;
bool find(int u)
{
vx[u] = true;
for(int i=1;i<=n;i++)
{
if(!vy[i] && g[u][i]==dx[u]+dy[i])
{
vy[i] = true;
if(dis[i]==-1 || find(dis[i]))
{
dis[i] = u;
return true;
}
}
}
return false;
} int solve()
{
memset(dx,0,sizeof(dx));
memset(dy,0,sizeof(dy));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dx[i] = max(dx[i], g[i][j]);
}
}
for(int i=1;i<=n;i++)
{
while(1)
{
minn = INT_MAX;
memset(vx,false,sizeof(vx));
memset(vy,false,sizeof(vy));
if(find(i)) break;
else
{
for(int j=1;j<=n;j++)
{
if(vx[j])
{
for(int k=1;k<=n;k++)
{
if(!vy[k] && dx[j] + dy[k] - g[j][k]<minn)
{
minn = dx[j] + dy[k] - g[j][k];
}
}
}
}
for(int j=1;j<=n;j++)
{
if(vx[j]) dx[j]-=minn;
if(vy[j]) dy[j]+=minn;
}
} }
}
return 0;
} int main()
{
while(scanf("%d",&n)!=EOF)
{ memset(g,0,sizeof(g));
memset(dis,-1,sizeof(dis));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&g[i][j]);
}
} res = 0;
solve();
for(int i=1;i<=n;i++)
{
if(dis[i]>0) res+=(dx[dis[i]]+dy[i]);
}
printf("%d\n",res);
}
return 0;
}
我也是醉了，找了一天的BUG
版权声明：本文为博主原创文章，未经博主允许不得转载。