题意：
给一个n*n的矩阵，每个格子中有正整数w[i][j]，试为每行和每列分别确定一个数字row[i]和col[i]，使得任意格子w[i][j]<=row[i]+col[j]恒成立。先输row，再输出col，再输出全部总和（总和应尽量小）。
思路：
本题与匹配无关，但可以用KM算法解决。
KM算法中的顶标就是保持了Lx[i]+ly[j]>=g[i][j]再求最大权和匹配的，但这个最大权和并没有关系。我们可以将row[i]看成一个男的，col[i]看成一个女的，这样男女的总数就相等。
一般来说，Lx[i]或Ly[i]仅需要取该行/列中最大的那个数即可保证满足要求，但是这样太大了，可以通过调整来使得总和更小。而KM算法的过程就是一个调整的过程，每一对匹配的男女的那条边的权值就会满足等号 w[i][j]=row[i]+col[j]，至少需要一个来满足等号，这样才能保证row[i]+col[j]是达到最小的，即从j列看，col[j]满足条件且最小，从i行看，row[i]满足条件且最小。这刚好与KM算法求最大权和一样。
#include <bits/stdc++.h>
#define LL long LONG_LONG_MAX
#define INF 0x7f7f7f7f
#define LL long long
using namespace std;
const int N=; int grid[N][N], girl[N];
int Lx[N], Ly[N], slack[N];
bool S[N], T[N];
int n; bool DFS(int x)
{
S[x]=true;
for(int i=; i<=n; i++)
{
if(T[i]) continue;
int tmp=Lx[x]+Ly[i]-grid[x][i];
if(tmp==)
{
T[i]=true;
if(girl[i]== || DFS(girl[i]))
{
girl[i]=x;
return true;
}
}
else if(tmp<slack[i])
slack[i]=tmp;
}
return false;
} int KM()
{
memset(girl, , sizeof(girl));
memset(Lx, , sizeof(Lx));
memset(Ly, , sizeof(Ly));
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
Lx[i]=max(Lx[i], grid[i][j]); for(int i=; i<=n; i++) //对于每个树
{
for(int j=; j<=n; j++) slack[j]=INF;
while()
{
memset(S, , sizeof(S));
memset(T, , sizeof(T));
if( DFS(i) ) break; //找到匹配的蚂蚁 int d=INF;
for(int j=; j<=n; j++) //找最小D
{
if(!T[j] && d>slack[j])
d=slack[j];
} for(int j=; j<=n; j++) //更新树
{
if(S[j])
Lx[j]-=d;
} for(int j=; j<=n; j++) //更新蚂蚁
{
if(T[j]) Ly[j]+=d;
else slack[j]-=d;
}
}
}
int sum=;
for(int i=; i<=n; i++) sum+=Lx[i]+Ly[i];
return sum;
} int main()
{
freopen("input.txt", "r", stdin);
while(~scanf("%d",&n))
{
memset(grid, , sizeof(grid));
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
scanf("%d",&grid[i][j]); int ans=KM();
printf("%d", Lx[]);//值得注意的输出格式。
for(int i=; i<=n; i++) printf(" %d", Lx[i]);
printf("\n");
printf("%d",Ly[]);
for(int i=; i<=n; i++) printf(" %d", Ly[i]);
printf("\n");
printf("%d\n", ans);
}
return ;
}
AC代码