题目
做法
(KM)好题啊，满足所有边(l(x)+l(y)≥w(x,y))(个人理解，如不对请及时留言)，这样能满足(sumlimits_i^n(l(x)+l(y)))最小值
My complete code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn=1e3,inf=0x3f3f3f3f;
LL n,mi;
LL lx[maxn],ly[maxn],w[maxn][maxn],mat[maxn];
bool S[maxn],T[maxn];
bool Match(LL u){
S[u]=true;
for(LL i=1;i<=n;++i){
if(!T[i]){
LL tmp(lx[u]+ly[i]-w[u][i]);
if(!tmp){
T[i]=true;
if(!mat[i] || Match(mat[i])){
mat[i]=u;
return true;
}
}
else
mi=min(mi,tmp);
}
}return false;
}
inline void Update(){
for(LL i=1;i<=n;++i)
if(S[i]) lx[i]-=mi;
for(LL i=1;i<=n;++i)
if(T[i]) ly[i]+=mi;
}
inline void KM(){
for(LL i=1;i<=n;++i){
mat[i]=lx[i]=ly[i]=0;
for(LL j=1;j<=n;++j)
lx[i]=max(lx[i],w[i][j]);
}
for(LL i=1;i<=n;++i){
while(true){
for(LL i=1;i<=n;++i)
S[i]=T[i]=false;
mi=inf;
if(Match(i)) break;
else Update();
}
}
}
int main(){
while(scanf("%d",&n)!=EOF&&n){
for(LL i=1;i<=n;++i)
for(LL j=1;j<=n;++j)
cin>>w[i][j];
KM();
LL ans(0);
for(LL i=1;i<=n;++i)
ans+=lx[i];
for(LL i=1;i<=n;++i)
ans+=ly[i];
printf("%d",lx[1]);
for(LL i=2;i<=n;++i)
printf(" %d",lx[i]);printf("
");
printf("%d",ly[1]);
for(LL i=2;i<=n;++i)
printf(" %d ",ly[i]);printf("
");
printf("%d
",ans);
}return 0;
}