layout: post
title: 训练指南 UVA - 11383（KM算法的应用 lx+ly >=w(x,y)）
author: "luowentaoaa"
catalog: true
mathjax: true
tags:
- KM算法
- 训练指南
Golden Tiger Claw
题意
给一个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算法的过程就是一个调整的过程，每一对匹配的男女的那条边的权值就会满足等号 wi[j]=row[i]+col[j]，至少需要一个来满足等号，这样才能保证row[i]+col[j]是达到最小的，即从j列看，col[j]满足条件且最小，从i行看，row[i]满足条件且最小。这刚好与KM算法求最大权和一样。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=5e2+50;
const ll inf=1e10;
const ll INF = 1000000000;
const double eps=1e-5;
int g[530][530]; ///存图
int nx,ny; /// 两边点数
bool visx[maxn],visy[maxn];
int slack[maxn];
int linker[maxn]; ///y中各点匹配状态
int lx[maxn],ly[maxn]; /// x,y中的点标号
bool dfs(int x){
visx[x]=true;
for(int y=0;y<ny;y++){
if(visy[y])continue;
int tmp=lx[x]+ly[y]-g[x][y];
if(tmp==0){
visy[y]=true;
if(linker[y]==-1||dfs(linker[y])){
linker[y]=x;return true;
}
}
else if(slack[y]>tmp)slack[y]=tmp;
}
return false;
}
int KM(){
memset(linker,-1,sizeof(linker));
memset(ly,0,sizeof(ly));
for(int i=0;i<nx;i++){
lx[i]=-inf;
for(int j=0;j<ny;j++){
if(g[i][j]>lx[i])lx[i]=g[i][j];
}
}
for(int x=0;x<nx;x++){
for(int i=0;i<ny;i++)slack[i]=inf;
while(true){
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
if(dfs(x))break;
int d=inf;
for(int i=0;i<ny;i++)
if(!visy[i]&&d>slack[i])d=slack[i];
for(int i=0;i<nx;i++)
if(visx[i])lx[i]-=d;
for(int i=0;i<ny;i++)
if(visy[i])ly[i]+=d;
else slack[i]-=d;
}
}
int res=0;
for(int i=0;i<ny;i++)
if(linker[i]!=-1)res+=g[linker[i]][i];
return res;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
while(cin>>n){
nx=ny=n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)cin>>g[i][j];
int ans=KM();
cout<<lx[0];
for(int i=1;i<n;i++)cout<<" "<<lx[i];cout<<endl;
cout<<ly[0];
for(int i=1;i<n;i++)cout<<" "<<ly[i];cout<<endl;
cout<<ans<<endl;
}
return 0;
}