首页 > 代码库 > 二分图多重匹配
二分图多重匹配
在二分图的最大匹配中，每个点（不管是X集合还是Y集合）最多只能与一条匹配边相关联，
然而，经常有这种问题，即二分图的一个点可以和多条匹配边相关联，但有上限，即cap[i]表示点i最多能和cap[i]条匹配边相关联。
hdu 3605
题意：2012来了，n个人可以逃往m个星球中的k个，每个星球都有上限，问所有的人能不能都都逃亡成功；
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已经匹配了n个人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 else26 {27 for(int j=0; j<cap[i]; ++j)//寻找增广路，可以从u出发，经过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个人，m个组，没个人适合m个组中的k个，由给定的数据说明，
要求分组后，人最多的那个组是所有可能情况中最小的
组的人数的情况可能是0--->n ，但是一个一个枚举太耗时了，所以用二分枚举最大组的容量上限，剩下的代码就都和上面那题一样
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;//二分枚举最大组的容量上限为limit77 if(MulMatch())78 {79 ans = limit;80 high = limit - 1;81 }82 else83 low = limit + 1;84 }85 printf("%d\n",ans);86 }87 return 0;88 }
二分图多重匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。