学步园

http://poj.org/problem?id=1469

求最大匹配。

code1:（匈牙利算法，寻找增广路的思想。）

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 300 + 5;
vector<int> g[MAXN];
int from[MAXN], tot;
bool use[MAXN];
int n;

bool match(int x)
{
    for(int i = 0; i < g[x].size(); ++i)
        if(!use[g[x][i]]) {
            use[g[x][i]] = true;
            if(from[g[x][i]] == -1 || match(from[g[x][i]])) {
                from[g[x][i]] = x;
                return true;
            }
        }
    return false;
}

int hungary()
{
    tot = 0;
    memset(from, -1, sizeof from );
    for(int i=1; i<=n; ++i) {
        memset(use, 0, sizeof use);
        if(match(i))
            ++tot;
    }
    return tot;
}

void init()
{
    int i, k, m, x;
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; ++i) {
        scanf("%d",&k);
        g[i].clear();
        while(k--) {
            scanf("%d",&x);
            g[i].push_back(x);
        }
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--) {
        init();
        if(n == hungary()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

code2:（Hopcroft-Karp算法）

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int maxn = 300 + 5;
int n1, n2;
vector<int> g[maxn];
int mx[maxn], my[maxn];
queue<int> que;
int dx[maxn], dy[maxn];
bool vis[maxn];

bool find(int u)
{
    for(int i=0; i<g[u].size(); ++i)
        if(!vis[g[u][i]] && dy[g[u][i]] == dx[u] + 1) {
            vis[g[u][i]] = true;
            if(!my[g[u][i]] || find(my[g[u][i]])) {
                mx[u] = g[u][i];
                my[g[u][i]] = u;
                return true;
            }
        }
    return false;
}

int matching()
{
    memset(mx, 0, sizeof mx );
    memset(my, 0, sizeof my );
    int ans = 0;
    while(true) {
        bool flag = false;
        while(!que.empty()) que.pop();
        memset(dx, 0, sizeof dx );
        memset(dy, 0, sizeof dy );
        for(int i=1; i<=n1; ++i)
            if(!mx[i]) que.push(i);
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            for(int i= 0; i<g[u].size(); ++i)
                if(!dy[g[u][i]]) {
                    dy[g[u][i]] = dx[u] + 1;
                    if(my[g[u][i]]) {
                        dx[my[g[u][i]]] = dy[g[u][i]] + 1;
                        que.push(my[g[u][i]]);
                    } else
                        flag = true;
                }
        }
        if(!flag) break;
        memset(vis, 0, sizeof vis );
        for(int i=1; i<=n1; ++i)
            if(!mx[i] && find(i)) ans++;
    }
    return ans;
}

void init()
{
    int i, k, m, x;
    scanf("%d%d",&n1,&m);
    for(i=1; i<=n1; ++i) {
        scanf("%d",&k);
        g[i].clear();
        while(k--) {
            scanf("%d",&x);
            g[i].push_back(x);
        }
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--) {
        init();
        if(n1 == matching()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}