题目:给牛找棚,每个棚只能容一只牛,牛在对应的棚才能产奶,问最多能让几只牛产奶。
/************************************************ Author :DarkTong Created Time :2016/7/31 10:51:05 File Name :Poj_1274.cpp *************************************************///#include <bits/stdc++.h> #include <cstdio> #include <cstring> using namespace std; const int maxn = 200 + 10; int w[maxn][maxn], n, m; int Left[maxn]; bool used[maxn]; bool match(int i) {for(int j=1;j<=n;++j) if(w[j][i]&&!used[j]){used[j] = true;if(!Left[j]||match(Left[j])){Left[j] = i;return true;}}return false; } //返回最大匹配数 int hungary() {int res=0;memset(Left, 0, sizeof(Left));for(int i=1;i<=m;++i){memset(used, 0, sizeof(used));if(match(i)) res++;}return res; }int main() {int T, cas=1;while(scanf("%d%d", &m, &n)==2){memset(w, 0, sizeof(w));int t, x;for(int i=1;i<=m;++i){scanf("%d", &t);for(int j=1;j<=t;++j){scanf("%d", &x);w[x][i]=1;}}printf("%d\n", hungary());}return 0; }