首页 > 代码库 > POJ 1274 The Perfect Stall【二分图最大匹配】

POJ 1274 The Perfect Stall【二分图最大匹配】

题意:二分图最大匹配

分析:二分图最大匹配

代码:

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6  7 const int maxn = 205; 8 int n; 9 10 int Link[maxn];11 int vis[maxn];12 vector<int> G[maxn];13 bool Find(int u) {14     for(int i = 0; i < G[u].size(); i++) {15         int v = G[u][i];16         if(!vis[v]) {17             vis[v] = 1;18             if(Link[v] == -1 || Find(Link[v])) {19                 Link[v] = u;20                 return true;21             }22         }23     }24     return false;25 }26 27 int solve() {28     int cnt = 0;29     memset(Link, -1, sizeof(Link));30     for(int i = 1; i <= n; i++) {31         if(G[i].size()) {32             memset(vis, 0, sizeof(vis));33             if(Find(i)) cnt++;34         }35     }36     return cnt;37 }38 39 int main() {40     int m;41     int num,_num;42     while(EOF != scanf("%d %d",&n, &m)) {43         for(int i = 1; i <= n; i++) {44             G[i].clear();45             scanf("%d",&num);46             for(int j = 0; j < num; j++) {47                 scanf("%d",&_num);48                 G[i].push_back(_num);49             }50         }51         printf("%d\n",solve());52     }53     return 0;54 }
View Code