POJ-1469 COURSES (匈牙利算法

题目大意：输入两个数n m，然后下面n行，每行第一个数代表后面有多少个数，后面的数代表和第i行的i可以匹配，一个人可以和多个学科匹配但是可能重复，问是否每个都能找到一个匹配。

for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &x);
            for(int j = 1; j <= x; ++j)
            {
                scanf("%d", &y);
                f[ i ][ y ] = 1;
            }
        }

题目思路：匈牙利算法，遇到无法匹配的如何已经被匹配就看看之前的能否换个进行匹配。

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn = 1e5 + 10;
 6 const int inf = 0x3f3f3f3f;
 7 
 8 int color[305], f[305][305], link[305]; // 是否选过，匹配图，选它的是谁（0说明还没被选）
 9 int m;
10 
11 int findy(int x) // 算法核心
12 {
13     for(int i = 1; i <= m; ++i)
14     {
15         if(f[x][i] && !color[i]) 
16         {
17             color[i] = 1;
18             if(link[i] == 0 || findy(link[i])) // 如果i被之前的人选了的话就看看之前的是否能换个选
19             {
20                 link[i] = x;
21                 return 1;
22             }
23         }
24     }
25     return 0;
26 }
27 
28 int main()
29 {
30     int t, n, x, y, ans;
31     scanf("%d", &t);
32     while(t--)
33     {
34         scanf("%d%d", &n, &m);
35         memset(f, 0, sizeof(f));
36         memset(link, 0, sizeof(link));
37 
38         for(int i = 1; i <= n; ++i)
39         {
40             scanf("%d", &x);
41             for(int j = 1; j <= x; ++j)
42             {
43                 scanf("%d", &y);
44                 f[i][y] = 1;
45             }
46         }
47         ans = 0;
48         for(int i = 1; i <= n; ++i)
49         {
50             memset(color, 0, sizeof(color)); // 每次进行下个时 记得更新
51             if(findy(i)) ans++;
52         }
53         if(ans == n) cout<<"YES"<<endl;
54         else cout<<"NO"<<endl;
55     }
56     return 0;
57 }