二分图匹配（入门） 之 poj 1274

//  [5/29/2014 Sjm]
/**********************************************************************
初次学习二分图匹配，参考的资料如下：                                     
https://www.byvoid.com/blog/hungary/ （图以及伪代码很棒）          
http://blog.csdn.net/Hackbuteer1/article/details/7398008 （基础知识点）
http://www.matrix67.com/blog/archives/39 （对算法的解释一语中的，太牛了）
http://blog.csdn.net/dark_scope/article/details/8880547/（根据这个模拟一下算法，可以对算法细节更了解）
将所有知识点整理如下。。。
*///*******************************************************************
/*
二分图匹配
 
基础：
1)二分图：
所有顶点可以分成两个集合X和Y，其中X或Y中任意两个在同一集合中的点都不相连，
所有的边关联在两个顶点中，恰好一个属于集合Ｘ，另一个属于集合Ｙ。
 
2)图的最大匹配
给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
图中包含边数最多的匹配称为图的最大匹配。
 
定义:
1) 未盖点：设Vi是图G的一个顶点，如果Vi 不与任意一条属于匹配M的边相关联，就称Vi 是一个未盖点。
2) 交错路：设P是图G的一条路，如果P的任意两条相邻的边一定是一条属于M而另一条不属于M，就称P是一条交错路。
3) 可增广路：两个端点都是未盖点的交错路叫做可增广路。
 
二分图最大匹配匈牙利算法思路：
1) 初始时最大匹配为空
2) while 找得到增广路径
	do 把增广路径加入到最大匹配中去
******************************************************************************************************************
匈牙利算法本质思想：
从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过，
再下一条又没匹配这样交替地出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，
把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。
不断执行上述操作，直到找不到这样的路径为止。
******************************************************************************************************************
*/

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

int V;  // 顶点数
vector<int> G[MAX_V]; // 图的邻接表表示
int myMatch[MAX_V]; // 所匹配的顶点
bool used[MAX_V];   // DFS 中 用到的访问标记

// 向图中增加一条连接 u 和 v 的边
void Add_edge(int u, int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}

//通过 DFS 寻找增广路
bool Dfs(int v)
{
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
        // 列举 v 能关联到的顶点 
        int u = G[v][i], w = myMatch[u];
        if (w < 0  // u 是未盖点
            || (!used[w] && Dfs(w)) // 从 u 的对应项出发有可增广路
            ) 
        {
            myMatch[v] = u;
            myMatch[u] = v;
            return true;
        }
    }
    return false;
}

int Bip_mat()
{
    int res = 0;
    memset(myMatch, -1, sizeof(myMatch));
    for (int v = 0; v < V; v++) {
        // 从未盖点出发（据可增广路定义知）
        if (myMatch[v] < 0) {
            memset(used, 0, sizeof(used));
            if (Dfs(v)) {
                res++;
            }
        }
    }
    return res;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    while (~scanf("%d %d", &N, &M))
    {
        V = N + M;
        for (int i = 0; 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);
            }
        }
        printf("%d
", Bip_mat());
        for (int i = 0; i < (M + N); i++) {
            G[i].clear();
        }
    }
    return 0;
}