HDU 3605 Escape【二分图多重匹配】

题意：

有n个人去m个星球告诉你每个人想去哪些星球和每个星球最多容纳多少人，问能不能让所有人都满足

分析：

二分图多重匹配

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6 
 7 const int maxn = 100005;
 8 const int maxm = 15;
 9 
10 int cap[maxm];
11 int Link[maxm][maxn];
12 int vLink[maxm];
13 int mat[maxn][maxm];
14 int vis[maxm];
15 int n, m;
16 bool Find(int u) {
17     for(int i = 1; i <= m; i++) {
18         if(!vis[i] && mat[u][i]) {
19             int v = i;
20             vis[v] = 1;
21             if(vLink[v] < cap[v]) {
22                 Link[v][vLink[v]++] = u;
23                 return true;
24             }
25             for(int j = 0; j < vLink[v]; j++) {
26                 if(Find(Link[v][j])) {
27                     Link[v][j] = u;
28                     return true;
29                 }
30             }
31         }
32     }
33     return false;
34 }
35 
36 bool solve() {
37     memset(Link, 0, sizeof(Link));
38     memset(vLink, 0, sizeof(vLink));
39     for(int i = 1; i <= n; i++) {
40         memset(vis, 0, sizeof(vis));
41         if(!Find(i)) return false;
42     }
43     return true;
44 }
45 
46 int main() {
47     while(EOF != scanf("%d %d",&n, &m)) {
48         for(int i = 1; i <= n; i++) {
49             for(int j = 1; j <= m; j++) {
50                 scanf("%d",&mat[i][j]);
51             }
52         }
53         for(int i = 1; i <= m; i++) {
54             scanf("%d",&cap[i]);
55         }
56         if(solve()) puts("YES");
57         else puts("NO");
58     }
59     return 0;
60 }

View Code