首页 > 代码库 > HDU 3605 Escape【二分图多重匹配】

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

2024-07-18 11:26:05   221人阅读

题意：

有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

 


联系
我们