题目链接：
二分匹配，求最小权，只要一开始先取相反数，lx初始化的时候取无穷小。。。然后KM一敲，最后输出在取相反数就行了。。。
值得一提的是，我这种渣代码，竟然跑了个rank 1。。。orz。。。
View Code 1 #include2 const int MAXN=110; 3 const int inf=1<<30; 4 using namespace std; 5 int n,m; 6 int map[MAXN][MAXN]; 7 int lx[MAXN],ly[MAXN]; 8 int match[MAXN]; 9 bool visitx[MAXN],visity[MAXN];10 11 //匈牙利算法12 int Hungary(int u){13 visitx[u]=true;14 for(int i=1;i<=n;i++){15 if(!visity[i]&&lx[u]+ly[i]==map[u][i]){16 visity[i]=true;17 if(match[i]==-1||Hungary(match[i])){18 match[i]=u;19 return true ;20 }21 }22 }23 return false ;24 }25 26 void KM_prefect_match(){27 int tmp;28 for(int i=1;i<=n;i++){29 lx[i]=-inf;30 }31 memset(ly,0,sizeof(ly));32 for(int i=1;i<=n;i++){33 for(int j=1;j<=n;j++){34 lx[i]=max(lx[i],map[i][j]);35 }36 }37 for(int i=1;i<=n;i++)38 {39 while(1){40 memset(visitx,false,sizeof(visitx));41 memset(visity,false,sizeof(visity));42 if(Hungary(i))43 break;44 else {45 tmp=inf;46 for(int j=1;j<=n;j++)if(visitx[j]){47 for(int k=1;k<=n;k++){48 if(!visity[k]&&tmp>lx[j]+ly[k]-map[j][k]){49 tmp=lx[j]+ly[k]-map[j][k];50 }51 }52 }53 for(int j=1;j<=n;j++){54 if(visitx[j])55 lx[j]-=tmp;56 if(visity[j])57 ly[j]+=tmp;58 }59 }60 }61 }62 }63 64 int main(){65 while(~scanf("%d%d",&n,&m)){66 memset(match,-1,sizeof(match));67 for(int i=1;i<=n;i++){68 for(int j=1;j<=n;j++){69 map[i][j]=-inf;70 }71 }72 for(int i=1;i<=m;i++){73 int x,y,w;74 scanf("%d%d%d",&x,&y,&w);75 if(map[x][y]<-w){76 map[x][y]=-w;77 }78 }79 KM_prefect_match();80 int flag=false;81 int ans=0;82 for(int i=1;i<=n;i++){83 if(match[i]==-1||map[match[i]][i]==-inf){84 flag=true;85 break;86 }87 ans+=map[match[i]][i];88 }89 if(flag){90 printf("-1\n");91 }else 92 printf("%d\n",-ans);93 }94 return 0;95 }