有网站是做水果原产地代发的吗,信息化建设网站范本,金华网站建设团队,茶叶官网网站建设在二分图的最大匹配中#xff0c;每个点#xff08;不管是X集合还是Y集合#xff09;最多只能与一条匹配边相关联#xff0c; 然而#xff0c;经常有这种问题#xff0c;即二分图的一个点可以和多条匹配边相关联#xff0c;但有上限#xff0c;即cap[i]表示点i最多能和… 在二分图的最大匹配中每个点不管是X集合还是Y集合最多只能与一条匹配边相关联 然而经常有这种问题即二分图的一个点可以和多条匹配边相关联但有上限即cap[i]表示点i最多能和cap[i]条匹配边相关联。 hdu 3605 题意2012来了n个人可以逃往m个星球中的k个每个星球都有上限问所有的人能不能都都逃亡成功 1 #include stdio.h2 #include string.h3 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 i0; im; 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 j0; jcap[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 i0; in; 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(i0; in; i)
57 for(j0; jm; j)
58 scanf(%d,Map[i][j]);
59
60 for(i0; im; 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.h2 #include string.h3 #include vector4 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 vectorint G[nMax];
11 int n,m,limit;
12
13 void init()
14 {
15 for(int i0; in; i)
16 G[i].clear();
17 }
18 bool dfs(int u)
19 {
20 for(int i0; iG[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 j0; jlimit; 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 i0; in; 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(n0 m0)
62 break;
63 init();
64 for(i0; in; 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 } 转载于:https://www.cnblogs.com/justPassBy/p/4025031.html
