http://acm.hdu.edu.cn/showproblem.php?pid=1083
题意：一共有N个学生跟P门课程,一个学生可以任意选一门或多门课,问是否达成: 1.每个学生选的都是不同的课(即不能有两个学生选同一门课) 2.每门课都有一个代表(即P门课都被成功选过)
今天学姐讲匹配时讲的题目，初学匹配，对匹配还有很多不理解的地方。。
增广路径性质：
(1)有奇数条边。
(2)起点在二分图的左半边，终点在右半边。
(3)路径上的点一定是一个在左半边，一个在右半边，交替出现。（其实二分图的性质就决定了这一点，因为二分图同一边的点之间没有边相连，不要忘记哦。）
(4)整条路径上没有重复的点。
(5)起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。
最小点覆盖=最大匹配
#include <iostream> #include <stdio.h> #include <string.h> #include <string> #include <vector> #include <algorithm> #include <map> #include <queue> #include <stack> #include <math.h>using namespace std;#define met(a, b) memset(a, b, sizeof(a)) #define maxn 303 #define INF 0x3f3f3f3f const int MOD = 1e9+7;typedef long long LL; int v[maxn], used[maxn], G[maxn][maxn]; int p;int Hungary(int x) {for(int i=1; i<=p; i++){if(!v[i] && G[x][i]){v[i] = 1;if(!used[i] || Hungary(used[i])){used[i] = x;return 1;}}}return 0; }int main() {int T, n, cnt, x;scanf("%d", &T);while( T --){met(G, 0);scanf("%d %d", &p, &n);for(int i=1; i<=p; i++){scanf("%d", &cnt);for(int j=1; j<=cnt; j++){scanf("%d", &x);G[x][i] = 1;}}met(used, 0);int ans = 0;for(int i=1; i<=n; i++){met(v, 0);if(Hungary(i))ans ++;}if(ans == p) puts("YES");else puts("NO");}return 0; }
