https://vjudge.net/problem/UVA-11383
题意:
给定一个N×N矩阵，每个格子里都有一个正整数W（i，j）。你的任务是给每行确定一个整数row（i），每列也确定一个整数col（i），使得对于任意格子（i，j），w（i，j）<=row（i）+col（j）。所有的row（i）和col（i）只和应尽量小。
思路：
利用二分图最佳完美匹配当中的l（x）+l（y）>=w（i，j），直接用KM算法即可。
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
const int maxn=+; int W[maxn][maxn], n;
int Lx[maxn];
int Ly[maxn];
int Left[maxn];
bool S[maxn], T[maxn]; bool Match(int i)
{
S[i] = true;
for (int j = ; j <= n; j++)
{
if (Lx[i] + Ly[j] == W[i][j] && !T[j])
{
T[j] = true;
if (!Left[j] || Match(Left[j]))
{
Left[j] = i;
return true;
}
}
}
return false;
} void Update()
{
int a = << ;
for (int i = ; i <= n; i++)
{
if (S[i])
{
for (int j = ; j <= n; j++)
{
if (!T[j])
{
a = min(a, Lx[i] + Ly[j] - W[i][j]);
}
}
}
}
for (int i = ; i <= n; i++)
{
if (S[i])
Lx[i] -= a;
if (T[i])
Ly[i] += a;
}
} void KM()
{
for (int i = ; i <= n; i++)
{
Left[i] = ;
Lx[i] = ;
Ly[i] = ;
for (int j = ; j <= n; j++)
{
Lx[i] = max(Lx[i], W[i][j]);
}
}
for (int i = ; i <= n; i++)
{
while (true)
{
memset(S, , sizeof(S));
memset(T, , sizeof(T));
if (Match(i))
break;
else
Update();
}
}
} int main()
{
//freopen("D:\\input.txt","r",stdin);
while(~scanf("%d",&n))
{
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
scanf("%d",&W[i][j]);
}
int ans=;
KM();
for(int i=;i<=n;i++)
{
printf("%d%c", Lx[i], i == n ? '\n' : ' ');
ans+=Lx[i];
}
for(int i=;i<=n;i++)
{
printf("%d%c", Ly[i], i == n ? '\n' : ' ');
ans+=Ly[i];
}
printf("%d\n",ans);
}
return ;
}