尴尬。。。理解不太好T T
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f const int maxn=; int n;
//标杆序号
int lx[maxn],ly[maxn];
//是否被搜索过
bool sx[maxn],sy[maxn];
int weight[maxn][maxn],mat[maxn]; inline int maxx(const int &n1,const int &n2){
return n1>n2?n1:n2;
} bool dfs(int x){
sx[x]=;
for(int i=;i<n;i++)
if(!sy[i]&&lx[x]+ly[i]==weight[x][i]){
sy[i]=;
if(mat[i]==-||dfs(mat[i])){
mat[i]=x;
return ;
}
}
return ;
} //x==0最小
//x==1最大
int KM(int flag){
if(!flag)
for(int i=;i<n;i++)
for(int j=;j<n;j++)
weight[i][j]=-weight[i][j];
memset(mat,-,sizeof mat);
//初始化标杆
for(int i=;i<n;i++){
lx[i]=-inf;
ly[i]=;
for(int i=;i<n;i++)
for(int j=;j<n;j++)
lx[i]=maxx(lx[i],weight[i][j]);
}
for(int i=;i<n;i++)
while(){
memset(sx,,sizeof sx);
memset(sy,,sizeof sy);
if(dfs(i)) break;
//修改标杆
int mic=inf;
for(int j=;j<n;j++)
if(sx[j])
for(int k=;k<n;k++)
if(!sy[k]&&lx[j]+ly[k]-weight[j][k]<mic)
mic=lx[j]+ly[k]-weight[j][k];
if(mic==) return -;
for(int j=;j<n;j++){
if(sx[j]) lx[j]-=mic;
if(sy[j]) ly[j]+=mic;
}
for(int j=;j<n;j++)
printf("%d ",lx[j]);
puts("");
for(int j=;j<n;j++)
printf("%d ",ly[j]);
puts("\n");
}
int sum=;
for(int i=;i<n;i++)
if(mat[i]>=)
sum+=weight[mat[i]][i];
if(!flag) sum=-sum;
return sum;
} int main(){
scanf("%d",&n);
for(int i=;i<n;i++)
for(int j=;j<n;j++)
scanf("%d",&weight[i][j]);
printf("%d\n",KM());
return ;
}
/*
5
3 4 6 4 9
6 4 5 3 8
7 5 3 4 2
6 3 2 2 5
8 4 5 4 7 KM(1)=29
*/