?

在二分圖的最大匹配中，每個(gè)點(diǎn)（不管是X集合還是Y集合）最多只能與一條匹配邊相關(guān)聯(lián)，

然而，經(jīng)常有這種問題，即二分圖的一個(gè)點(diǎn)可以和多條匹配邊相關(guān)聯(lián)，但有上限，即cap[i]表示點(diǎn)i最多能和cap[i]條匹配邊相關(guān)聯(lián)。

?

hdu 3605

題意：2012來了，n個(gè)人可以逃往m個(gè)星球中的k個(gè)，每個(gè)星球都有上限，問所有的人能不能都都逃亡成功；

?

?

1 #include <stdio.h> 2 #include <string.h> 3 const int N = 100000 + 10; 4 const int M = 10 + 10; 5 int n,m; 6 int Map[N][M]; 7 int cap[M];//星球i的容量上限 8 int cy[M][N]; 9 int num[M];//num[i]記錄星球i已經(jīng)匹配了n個(gè)人 10 bool vis[M]; 11 12 13 bool dfs(int u) 14 { 15 for(int i=0; i<m; ++i) 16 { 17 if(!vis[i] && Map[u][i]) 18 { 19 vis[i] = true; 20 if(num[i] < cap[i]) 21 { 22 cy[i][num[i]++] = u; 23 return true; 24 } 25 else 26 { 27 for(int j=0; j<cap[i]; ++j)//尋找增廣路，可以從u出發(fā)，經(jīng)過n條匹配邊中的一條找到增廣路就行 28 { 29 if(dfs(cy[i][j])) 30 { 31 cy[i][j] = u; 32 return true; 33 } 34 } 35 } 36 } 37 } 38 return false; 39 } 40 bool MulMatch() 41 { 42 memset(num, 0, sizeof(num)); 43 for(int i=0; i<n; ++i) 44 { 45 memset(vis, 0, sizeof(vis)); 46 if(!dfs(i)) 47 return false; 48 } 49 return true; 50 } 51 int main() 52 { 53 int i,j; 54 while(scanf("%d%d",&n,&m)!=EOF) 55 { 56 for(i=0; i<n; ++i) 57 for(j=0; j<m; ++j) 58 scanf("%d",&Map[i][j]); 59 60 for(i=0; i<m; ++i) 61 scanf("%d",&cap[i]); 62 printf("%s\n",MulMatch()?"YES":"NO"); 63 } 64 65 return 0; 66 }

?hdu 1669

題意：給定n個(gè)人，m個(gè)組，沒個(gè)人適合m個(gè)組中的k個(gè)，由給定的數(shù)據(jù)說明，
要求分組后，人最多的那個(gè)組是所有可能情況中最小的

組的人數(shù)的情況可能是0--->n ?，但是一個(gè)一個(gè)枚舉太耗時(shí)了，所以用二分枚舉最大組的容量上限，剩下的代碼就都和上面那題一樣

1 #include <stdio.h> 2 #include <string.h> 3 #include <vector> 4 using namespace std; 5 const int nMax = 1000 + 10; 6 const int mMax = 555 + 10; 7 int num[mMax]; 8 bool vis[mMax]; 9 int cy[mMax][nMax]; 10 vector<int> G[nMax]; 11 int n,m,limit; 12 13 void init() 14 { 15 for(int i=0; i<n; ++i) 16 G[i].clear(); 17 } 18 bool dfs(int u) 19 { 20 for(int i=0; i<G[u].size(); ++i) 21 { 22 int v = G[u][i]; 23 if(!vis[v]) 24 { 25 vis[v] = true; 26 if(num[v] < limit) 27 { 28 cy[v][num[v]++] = u; 29 return true; 30 } 31 for(int j=0; j<limit; ++j) 32 if(dfs(cy[v][j])) 33 { 34 cy[v][j] = u; 35 return true; 36 } 37 38 } 39 } 40 return false; 41 } 42 bool MulMatch() 43 { 44 memset(num, 0, sizeof(num)); 45 memset(cy, 0, sizeof(cy)); 46 for(int i=0; i<n; ++i) 47 { 48 memset(vis, 0, sizeof(vis)); 49 if(!dfs(i)) 50 return false; 51 } 52 return true; 53 } 54 int main() 55 { 56 char str[20]; 57 int i,j; 58 while(true) 59 { 60 scanf("%d%d",&n,&m); 61 if(n==0 && m==0) 62 break; 63 init(); 64 for(i=0; i<n; ++i) 65 { 66 scanf("%s",str); 67 while( getchar()==' ') 68 { 69 scanf("%d",&j); 70 G[i].push_back(j); 71 } 72 } 73 int low = 0, high = n,ans = 0; 74 while(low <= high) 75 { 76 limit = (low + high) >> 1;//二分枚舉最大組的容量上限為limit 77 if(MulMatch()) 78 { 79 ans = limit; 80 high = limit - 1; 81 } 82 else 83 low = limit + 1; 84 } 85 printf("%d\n",ans); 86 } 87 return 0; 88 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/justPassBy/p/4025031.html

總結(jié)

以上是生活随笔為你收集整理的二分图多重匹配的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。