带权二分图最大权完美匹配。
裸的km算法。
注意开long long。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 5 using namespace std; 6 7 const long long INF = 99999999999999999; 8 int n, match[21]; 9 long long p[21][21], q[21][21], love[21][21], ex_boy[21], ex_girl[21], slack[21]; 10 bool vis_boy[21], vis_girl[21]; 11 12 bool find(int i) 13 { 14 int j; 15 long long gap; 16 vis_girl[i] = 1; 17 for(j = 1; j <= n; j++) 18 { 19 if(vis_boy[j]) continue; 20 gap = ex_girl[i] + ex_boy[j] - love[i][j]; 21 if(gap == 0) 22 { 23 vis_boy[j] = 1; 24 if(match[j] == -1 || find(match[j])) 25 { 26 match[j] = i; 27 return 1; 28 } 29 } 30 else slack[j] = min(slack[j], gap); 31 } 32 return 0; 33 } 34 35 long long KM() 36 { 37 int i, j; 38 long long d, ret = 0; 39 memset(match, -1, sizeof(match)); 40 for(i = 1; i <= n; i++) 41 for(j = 1; j <= n; j++) 42 ex_girl[i] = max(ex_girl[i], love[i][j]); 43 for(i = 1; i <= n; i++) 44 { 45 for(j = 1; j <= n; j++) slack[j] = INF; 46 while(1) 47 { 48 memset(vis_boy, 0, sizeof(vis_boy)); 49 memset(vis_girl, 0, sizeof(vis_girl)); 50 if(find(i)) break; 51 d = INF; 52 for(j = 1; j <= n; j++) 53 if(!vis_boy[j]) 54 d = min(d, slack[j]); 55 for(j = 1; j <= n; j++) 56 { 57 if(vis_boy[j]) ex_boy[j] += d; 58 if(vis_girl[j]) ex_girl[j] -= d; 59 } 60 } 61 } 62 for(i = 1; i <= n; i++) ret += love[match[i]][i]; 63 return ret; 64 } 65 66 int main() 67 { 68 int i, j; 69 scanf("%d", &n); 70 for(i = 1; i <= n; i++) 71 for(j = 1; j <= n; j++) 72 scanf("%lld", &p[i][j]); 73 for(i = 1; i <= n; i++) 74 for(j = 1; j <= n; j++) 75 scanf("%lld", &q[i][j]); 76 for(i = 1; i <= n; i++) 77 for(j = 1; j <= n; j++) 78 love[i][j] = p[i][j] * q[j][i]; 79 printf("%lld", KM()); 80 return 0; 81 }