Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 17652 Accepted Submission(s): 7436
抱着试一试的心态读了一下题,果然是裸模版题...敲了一波就过了
1 /************************************************************************* 2 > File Name: hdu-2255.奔小康赚大钱.cpp 3 > Author: CruelKing 4 > Mail: 2016586625@qq.com 5 > Created Time: 2019年09月04日 星期三 00时01分32秒 6 本题思路:最大权完备匹配裸题 7 ************************************************************************/ 8 9 #include <cstdio> 10 #include <cstring> 11 using namespace std; 12 13 const int maxn = 300 + 5, inf = 0x3f3f3f3f; 14 int n, g[maxn][maxn]; 15 int linker[maxn], lx[maxn], ly[maxn], slack[maxn]; 16 bool visy[maxn], visx[maxn]; 17 18 bool dfs(int x) { 19 visx[x] = true; 20 for(int y = 1; y <= n; y ++) { 21 if(visy[y]) continue; 22 int temp = lx[x] + ly[y] - g[x][y]; 23 if(temp == 0) { 24 visy[y] = true; 25 if(linker[y] == -1 || dfs(linker[y])) { 26 linker[y] = x; 27 return true; 28 } 29 } 30 else if(slack[y] > temp) slack[y] = temp; 31 } 32 return false; 33 } 34 35 int km() { 36 memset(linker, -1, sizeof linker); 37 memset(ly, 0, sizeof ly); 38 for(int i = 1; i <= n; i ++) { 39 lx[i] = -inf; 40 for(int j = 1; j <= n; j ++) 41 if(g[i][j] > lx[i]) lx[i] = g[i][j]; 42 } 43 for(int x = 1; x <= n; x ++) { 44 for(int i = 1; i <= n; i ++) 45 slack[i] = inf; 46 while(true) { 47 memset(visx, false, sizeof visx); 48 memset(visy, false, sizeof visy); 49 if(dfs(x)) break; 50 int d = inf; 51 for(int i = 1; i <= n; i ++) 52 if(!visy[i] && d > slack[i]) d = slack[i]; 53 for(int i = 1; i <= n; i ++) 54 if(visx[i]) lx[i] -= d; 55 for(int i = 1; i <= n; i ++) { 56 if(visy[i]) ly[i] += d; 57 else slack[i] -= d; 58 } 59 } 60 } 61 int res = 0; 62 for(int i = 1; i <= n; i ++) 63 if(linker[i] != -1) res += g[linker[i]][i]; 64 return res; 65 } 66 67 int main() { 68 while(~scanf("%d", &n)) { 69 for(int i = 1; i <= n; i ++) { 70 for(int j = 1; j <= n; j ++) { 71 scanf("%d", &g[i][j]); 72 } 73 } 74 printf("%d\n", km()); 75 } 76 return 0; 77 }
原文:https://www.cnblogs.com/bianjunting/p/11456575.html