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; }
?
