首页 > 代码库 > UVa 11383 少林决胜（二分图最佳完美匹配）
UVa 11383 少林决胜（二分图最佳完美匹配）
https://vjudge.net/problem/UVA-11383
题意:
给定一个N×N矩阵，每个格子里都有一个正整数W（i，j）。你的任务是给每行确定一个整数row（i），每列也确定一个整数col（i），使得对于任意格子（i，j），w（i，j）<=row（i）+col（j）。所有的row（i）和col（i）只和应尽量小。
思路：
利用二分图最佳完美匹配当中的l（x）+l（y）>=w（i，j），直接用KM算法即可。
1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<cstdio> 7 using namespace std; 8 const int maxn=500+5; 9 10 int W[maxn][maxn], n; 11 int Lx[maxn]; 12 int Ly[maxn]; 13 int Left[maxn]; 14 bool S[maxn], T[maxn]; 15 16 bool Match(int i) 17 { 18 S[i] = true; 19 for (int j = 1; j <= n; j++) 20 { 21 if (Lx[i] + Ly[j] == W[i][j] && !T[j]) 22 { 23 T[j] = true; 24 if (!Left[j] || Match(Left[j])) 25 { 26 Left[j] = i; 27 return true; 28 } 29 } 30 } 31 return false; 32 } 33 34 void Update() 35 { 36 int a = 1 << 30; 37 for (int i = 1; i <= n; i++) 38 { 39 if (S[i]) 40 { 41 for (int j = 1; j <= n; j++) 42 { 43 if (!T[j]) 44 { 45 a = min(a, Lx[i] + Ly[j] - W[i][j]); 46 } 47 } 48 } 49 } 50 for (int i = 1; i <= n; i++) 51 { 52 if (S[i]) 53 Lx[i] -= a; 54 if (T[i]) 55 Ly[i] += a; 56 } 57 } 58 59 void KM() 60 { 61 for (int i = 1; i <= n; i++) 62 { 63 Left[i] = 0; 64 Lx[i] = 0; 65 Ly[i] = 0; 66 for (int j = 1; j <= n; j++) 67 { 68 Lx[i] = max(Lx[i], W[i][j]); 69 } 70 } 71 for (int i = 1; i <= n; i++) 72 { 73 while (true) 74 { 75 memset(S, 0, sizeof(S)); 76 memset(T, 0, sizeof(T)); 77 if (Match(i)) 78 break; 79 else 80 Update(); 81 } 82 } 83 } 84 85 int main() 86 { 87 //freopen("D:\\input.txt","r",stdin); 88 while(~scanf("%d",&n)) 89 { 90 for(int i=1;i<=n;i++) 91 { 92 for(int j=1;j<=n;j++) 93 scanf("%d",&W[i][j]); 94 } 95 int ans=0; 96 KM(); 97 for(int i=1;i<=n;i++) 98 { 99 printf("%d%c", Lx[i], i == n ? ‘\n‘ : ‘ ‘);100 ans+=Lx[i];101 }102 for(int i=1;i<=n;i++)103 {104 printf("%d%c", Ly[i], i == n ? ‘\n‘ : ‘ ‘);105 ans+=Ly[i];106 }107 printf("%d\n",ans);108 }109 return 0;110 }
UVa 11383 少林决胜（二分图最佳完美匹配）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。