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

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注