UVA11383 二分图最佳匹配的性质的应用

 1 /*UVA11383
 2 二分图最佳匹配的性质的应用
 3 首先看这道题的题面：
 4 给定一个N*N的矩阵，每个格子上填上权值W[i][j];
 5 现在要求找到row[1]..row[n],和col[1]...col[n]。分别对应每一行和每一列。
 6 使得对于任意格子(i,j),W[i][j]<=row[i]+col[j]
 7 还要求出row[i]和col[i]总和的最小值
 8 而最优匹配（二分后的权值和最大）后，顶标数组会满足Lx(x)+Ly(y)>=W[x][y]这个条件，而sigm(Lx(i)+Ly(j))是最小的。
 9 */
10 #include <cmath>
11 #include <algorithm>
12 #include <stdlib.h>
13 #include <iostream>
14 #include <string.h>
15 #include <stdio.h>
16 #include <stack>
17 #include <set>
18 #include <map>
19 #include <vector>
20 #define typed int
21 #define INF 1<<30
22 #define maxn 550
23 #define eps 1e-6
24 using namespace std;
25 int n;
26 typed W[maxn][maxn];
27 typed Lx[maxn],Ly[maxn];//顶标
28 int lef[maxn];//由A到B的映射
29 bool S[maxn],T[maxn];
30 
31 bool match(int i){
32     S[i]=true;
33     for(int j=1;j<=n;j++) if (fabs(Lx[i]+Ly[j]-W[i][j])<eps && !T[j]){
34         T[j]=true;
35         if (!lef[j] || match(lef[j])){
36             lef[j]=i;
37             return true;
38         }
39     }
40     return false;
41 }
42 
43 void update(){
44     typed a=INF;
45     for(int i=1;i<=n;i++) if(S[i]){
46         for(int j=1;j<=n;j++) if(!T[j])
47             a=min(a,Lx[i]+Ly[j]-W[i][j]);
48     }
49     for(int i=1;i<=n;i++){
50         if (S[i]) Lx[i]-=a;
51         if (T[i]) Ly[i]+=a;
52     }
53 }
54 void KM(){
55     for(int i=1;i<=n;i++){
56         lef[i]=Lx[i]=Ly[i]=0;
57         for(int j=1;j<=n;j++){
58             Lx[i]=max(Lx[i],W[i][j]);
59         }
60     }
61     for(int i=1;i<=n;i++){
62         for(;;){
63             for(int j=1;j<=n;j++) S[j]=T[j]=false;
64             if (match(i)) break;else update();
65         }
66     }
67 }
68 int nextint(){
69     int x;
70     scanf("%d",&x);
71     return x;
72 }
73 void read(){
74     for(int i=1;i<=n;i++)
75     for(int j=1;j<=n;j++)
76     W[i][j]=nextint();
77 }
78 void printans(){
79     for(int i=1;i<=n;i++)
80     if (i<n) printf("%d ",Lx[i]);else printf("%d
",Lx[i]);
81     for(int i=1;i<=n;i++)
82     if (i<n) printf("%d ",Ly[i]);else printf("%d
",Ly[i]);
83     int sum=0;
84     for(int i=1;i<=n;i++) sum+=Lx[i]+Ly[i];
85     printf("%d
",sum);
86 }
87 int main(){
88     while(cin>>n){
89         read();
90         KM();
91         printans();
92     }
93     return 0;
94 }