?

?

?

題意：

　　給一個n*n的矩陣，每個格子中有正整數w[i][j]，試為每行和每列分別確定一個數字row[i]和col[i]，使得任意格子w[i][j]<=row[i]+col[j]恒成立。先輸row，再輸出col，再輸出全部總和（總和應盡量小）。

?

思路：

　　本題與匹配無關，但可以用KM算法解決。

　　KM算法中的頂標就是保持了Lx[i]+ly[j]>=g[i][j]再求最大權和匹配的，但這個最大權和并沒有關系。我們可以將row[i]看成一個男的，col[i]看成一個女的，這樣男女的總數就相等。

　　一般來說，Lx[i]或Ly[i]僅需要取該行/列中最大的那個數即可保證滿足要求，但是這樣太大了，可以通過調整來使得總和更小。而KM算法的過程就是一個調整的過程，每一對匹配的男女的那條邊的權值就會滿足等號 w[i][j]=row[i]+col[j]，至少需要一個來滿足等號，這樣才能保證row[i]+col[j]是達到最小的，即從j列看，col[j]滿足條件且最小，從i行看，row[i]滿足條件且最小。這剛好與KM算法求最大權和一樣。

?

?

1 #include <bits/stdc++.h> 2 #define LL long LONG_LONG_MAX 3 #define INF 0x7f7f7f7f 4 #define LL long long 5 using namespace std; 6 const int N=510; 7 8 int grid[N][N], girl[N]; 9 int Lx[N], Ly[N], slack[N]; 10 bool S[N], T[N]; 11 int n; 12 13 bool DFS(int x) 14 { 15 S[x]=true; 16 for(int i=1; i<=n; i++) 17 { 18 if(T[i]) continue; 19 int tmp=Lx[x]+Ly[i]-grid[x][i]; 20 if(tmp==0) 21 { 22 T[i]=true; 23 if(girl[i]==0 || DFS(girl[i])) 24 { 25 girl[i]=x; 26 return true; 27 } 28 } 29 else if(tmp<slack[i]) 30 slack[i]=tmp; 31 } 32 return false; 33 } 34 35 36 37 int KM() 38 { 39 memset(girl, 0, sizeof(girl)); 40 memset(Lx, 0, sizeof(Lx)); 41 memset(Ly, 0, sizeof(Ly)); 42 for(int i=1; i<=n; i++) 43 for(int j=1; j<=n; j++) 44 Lx[i]=max(Lx[i], grid[i][j]); 45 46 for(int i=1; i<=n; i++) //對于每個樹 47 { 48 for(int j=1; j<=n; j++) slack[j]=INF; 49 while(1) 50 { 51 memset(S, 0, sizeof(S)); 52 memset(T, 0, sizeof(T)); 53 if( DFS(i) ) break; //找到匹配的螞蟻 54 55 56 int d=INF; 57 for(int j=1; j<=n; j++) //找最小D 58 { 59 if(!T[j] && d>slack[j]) 60 d=slack[j]; 61 } 62 63 for(int j=1; j<=n; j++) //更新樹 64 { 65 if(S[j]) 66 Lx[j]-=d; 67 } 68 69 for(int j=1; j<=n; j++) //更新螞蟻 70 { 71 if(T[j]) Ly[j]+=d; 72 else slack[j]-=d; 73 } 74 } 75 } 76 int sum=0; 77 for(int i=1; i<=n; i++) sum+=Lx[i]+Ly[i]; 78 return sum; 79 } 80 81 82 83 84 int main() 85 { 86 freopen("input.txt", "r", stdin); 87 while(~scanf("%d",&n)) 88 { 89 memset(grid, 0, sizeof(grid)); 90 for(int i=1; i<=n; i++) 91 for(int j=1; j<=n; j++) 92 scanf("%d",&grid[i][j]); 93 94 int ans=KM(); 95 printf("%d", Lx[1]);//值得注意的輸出格式。 96 for(int i=2; i<=n; i++) printf(" %d", Lx[i]); 97 printf("\n"); 98 printf("%d",Ly[1]); 99 for(int i=2; i<=n; i++) printf(" %d", Ly[i]); 100 printf("\n"); 101 printf("%d\n", ans); 102 } 103 return 0; 104 } AC代碼

?

轉載于:https://www.cnblogs.com/xcw0754/p/4723861.html

總結

以上是生活随笔為你收集整理的UVA 11383 Golden Tiger Claw 金虎爪（KM算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。