首页 > 代码库 > POJ 1469 COURSES【二分图最大匹配】

POJ 1469 COURSES【二分图最大匹配】

分析:二分图最大匹配

代码:

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