hdu 3605(多重匹配）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3605

题意：

世界末日即将到来，地球上有n个人想转移到m个外星球，但是不同的人适应于不同的星球(1个人可适应多个星球)，每个外星球都有人数的限制，现在给你星球人数的上限。还有每个人不同的适应情况。问，能否安排所有的人都成功地转移到外星球上。

思路：多重匹配。。。

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define MAXN 100000+10
 6 #define MAXM 12
 7 
 8 bool map[MAXN][MAXM];
 9 int cap[MAXM];//i最多能匹配的上限
10 int link[MAXM];//i当前的匹配数
11 int vlink[MAXM][MAXN];//与i匹配的第j个匹配的数k;
12 bool mark[MAXM];//标记的是已匹配的planet;
13 int n,m;
14 
15 bool dfs(int k){
16     for(int i=1;i<=m;i++){
17         if(!mark[i]&&map[k][i]){
18             mark[i]=true;
19             if(link[i]<cap[i]){
20                 vlink[i][link[i]]=k;
21                 link[i]++;
22                 return true;
23             }
24             //如果没有满足匹配要求的，重新匹配
25             for(int j=0;j<link[i];j++){
26                 if(dfs(vlink[i][j])){
27                     vlink[i][j]=k;
28                     return true;
29                 }
30             }
31         }
32     }
33     return false;
34 }
35 
36 
37 int main(){
38     while(~scanf("%d%d",&n,&m)){
39         for(int i=1;i<=n;i++){
40             for(int j=1;j<=m;j++){
41                 scanf("%d",&map[i][j]);
42             }
43         }
44         for(int i=1;i<=m;i++)scanf("%d",&cap[i]);
45         memset(link,0,sizeof(link));
46         memset(vlink,0,sizeof(vlink));
47         bool flag=true;
48         for(int i=1;i<=n;i++){
49             memset(mark,false,sizeof(mark));
50             if(!dfs(i)){flag=false;break;}
51         }
52         flag?puts("YES"):puts("NO");
53     }
54     return 0;
55 }