最大流（多个源点，多个汇点） 之 poj 1274

//  [5/28/2014 Sjm]
/*
最大流：多个源点，多个汇点

// 若按二分图匹配做，请参见：http://www.cnblogs.com/shijianming/p/4140846.html
 
思路：
1）增加一个超级源点 S，从 S 向 每个源点 连一条容量为对应最大流出流量的边
2）增加一个超级汇点 T，从 每一个汇点 向 T 连一条容量为对应最大流入容量的边
 
对于此题：
源点 cows （范围：M+1 ~ M+N），汇点 stalls （范围：1 ~ M）
设 cows 与 the stalls （in which that cow is willing to produce milk）之间的容量为 1
1）设 0 为超级源点，
   因为每个 cow 流出的最大流出流量为 1（只能连一个stall），所以得：超级源点 向每个 cows 的连线的流量为 1
2）设 M+N+1 为超级汇点
   因为流入每个 stall 最大流量为 1(只能被一个cow连接)，所以得：每个 stall 向 超级汇点 的连线的连线的流量为 1
 
*/

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_V = 410;
const int INF = 0x3f3f3f3f;
int N, M;

struct edge { int to, cap, rev; };
vector<edge> G[MAX_V];
bool used[MAX_V];

void add_edge(int from, int to, int cap)
{
    edge e1 = { to, cap, G[to].size() };
    G[from].push_back(e1);
    edge e2 = { from, 0, G[from].size() - 1 };
    G[to].push_back(e2);
}

int dfs(int v, int t, int f)
{
    if (v == t) return f;
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
        edge &e = G[v][i];
        if (!used[e.to] && (e.cap > 0)) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int Solve(int s, int t)
{
    int flow = 0;
    for (;;)
    {
        memset(used, 0, sizeof(used));
        int f = dfs(s, t, INF);
        if (!f) return flow;
        flow += f;
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    while (~scanf("%d %d", &N, &M))
    {
        for (int i = 1; i <= N; i++) {
            int mycount;
            scanf("%d", &mycount);
            int tep;
            for (int j = 0; j < mycount; j++) {
                scanf("%d", &tep);
                add_edge(M + i, tep, 1);
            }
        }
        for (int i = 1; i <= N; i++) {
            add_edge(0, M+i, 1);
        }
        for (int i = 1; i <= M; i++) {
            add_edge(i, M + N + 1, 1);
        }
        printf("%d
", Solve(0, M + N + 1));
        for (int i = 0; i < MAX_V; i++) {
            G[i].clear();
        }
    }
    return 0;
}