POJ1274 二分图匹配
2017年7月29日题意是有 n 头奶牛, m 个槽,某个奶牛只偏爱到某些槽位去吃草.让你尽可能多地让奶牛到自己喜欢的槽位去.求最大能有多少头奶牛能到自己喜欢的槽位.
这不就是道裸的二分图匹配.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 205;
int m, n;
vector<int> G[N];
int vis[N];
int link[N];
bool match(int u)
{
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (vis[v])
continue;
vis[v] = 1;
if (link[v] == -1 || match(link[v])) {
link[v] = u;
return true;
}
}
return false;
}
int main()
{
while (~scanf("%d %d", &n, &m)) {
for (int i = 1; i <= n; i++) {
G[i].clear();
int x, y;
scanf("%d", &x);
while (x--) {
scanf("%d", &y);
G[i].push_back(y);
}
}
int ans = 0;
memset(link, -1, sizeof(link));
for (int i = 1; i <= n; i++) {
memset(vis, 0, sizeof(vis));
ans += match(i);
}
printf("%d\n", ans);
}
return 0;
}