UVA 11383 Golden Tiger Claw(最佳二分图完美匹配)

时间:2022-11-23 08:17:56

题意:在一个N*N的方格中,各有一个整数w(i,j),现在要求给每行构造row(i),给每列构造col(j),使得任意w(i,j)<=row(i)+col(j),输出row(i)与col(j)之和最小的方案。

当看到w(i,j)<=row(i)+col(j),并且row()col()都是自己构造的时候,就想到了二分匹配:w[i,j]<=Lx[i]+Ly[j]。直接套用模板,求最佳二分完美匹配,输出Lx[],Ly[],以及最小值即可。

 #include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define clr(a,m) memset(a,m,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std; const int MAXN=;
const int INF =1e9;
const double eps=1e-; int gap[MAXN][MAXN];
int Lx[MAXN],Ly[MAXN],slack[MAXN];
int left[MAXN],n;
bool S[MAXN],T[MAXN]; void read()
{
rep(i,,n)
rep(j,,n)
scanf("%d",&gap[i][j]);
} bool match(int u)
{
S[u]=true;
rep(v,,n)
if(!T[v]){
int tmp=Lx[u]+Ly[v]-gap[u][v];
if(tmp==){
T[v]=true;
if(!left[v]||match(left[v])){
left[v]=u;
return true;
}
}else slack[v]=min(slack[v],tmp);
}
return false;
} void update()
{
int a=INF;
rep(v,,n)
if(!T[v])
a=min(a,slack[v]);
rep(i,,n){
if(S[i])Lx[i]-=a;
if(T[i])Ly[i]+=a;
}
} void KM()
{
rep(i,,n){
left[i]=Ly[i]=;
Lx[i]=-INF;
rep(j,,n)
Lx[i]=max(Lx[i],gap[i][j]);
}
rep(i,,n){
rep(j,,n)
slack[j]=INF;
while()
{
rep(j,,n)
S[j]=T[j]=;
if(match(i))
break;
else
update();
}
}
} void print()
{
int ans=;
rep(i,,n){
ans+=Lx[i];
if(i!=)printf(" ");
printf("%d",Lx[i]); }
printf("\n");
rep(i,,n){
ans+=Ly[i];
if(i!=)printf(" ");
printf("%d",Ly[i]);
}
printf("\n");
printf("%d\n",ans);
} int main()
{
while(~scanf("%d",&n))
{
read();
KM();
print();
}
return ;
}