二分图最大匹配算法

好吧，看了好久还是没有看会，以后有机会再看看吧。

/*少说话，多做事*/
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>

/*
 二分图最大匹配算法：
 问题：给出一个二分图，找一个边数最大的匹配。就是选择尽量多的边，使得选中的边中任意两条边均没有公共点。如果没有的点都是匹配点那就是一个完美匹配
 解决方案：增广路定理
 增广路：从一个未匹配的点开始，依次走过未匹配边，匹配边，未匹配边，匹配边，。。。。如果最后的终点是一个未匹配点（即最后一条边是一条未匹配边），那么这条路就是一条增广路。而将增广路上的未匹配边和匹配边进行互换，就会使得匹配边多一条。
 由此可知，存在一条增广路就可以将匹配的边数加一。那么一个匹配是最大匹配的充要条件便是不存在增广路。此定理不仅仅适用于二分图。
 
 
 最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
 完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。显然，完美匹配一定是最大匹配，但是并非每个图都存在完美匹配。
 最小顶点覆盖：选取最少的点，使任意一条边至少有一个端点被选择（选取最少的点，使得点集中的点能覆盖所有的边）
 最大独立数：选取最多的点，使任意所选两点均不相连
 最小路径覆盖数：对于一个DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为0（即单个点）
 
 关于最大匹配数的一些结论：
 1.最大匹配数=最小顶点覆盖（选取最少的点，使得集中的点能覆盖所有的边）
 证明：首先要明确的一点是最小顶点覆盖一定不会小于最大匹配数。
 显而易见，最大匹配中的每一个匹配都是不相邻的一条边，如果最大匹配数为n，那么至少需要n个顶点来覆盖这n条边。
 2.顶点数-最小顶点覆盖=最小边覆盖（边最少的情况下，边集中的边覆盖所有的点）
 3.顶点数=最大匹配+最大独立集（点集，其中的点互不相连）
 
 匈牙利算法（二分图最大匹配算法）
 
例题：poj3041
 题意：在网格上给出一些点，每次可以清除一行或者一列的点，清除次数最少的情况下清除所有的点。用第一个结论最小顶点覆盖=最大匹配数
 思路：将行看做左点集，列看作右点集，若（i,j）存在障碍物，则在左i右j间连一条边。
 现在要在所建的二分图中，选择最少的点使得所有边都至少有一个点被选中，实质就是求最小覆盖数问题。
 总结：
 1.匈牙利算法寻找最大匹配，就是通过不断寻找原有匹配M的增广路径，因为找到一条M匹配的增广路径，就意味着一个更大的匹配M‘，其恰好比M多一条边。
 2.对于图来说，最大匹配不是唯一的，但是最大匹配的大小是唯一的。
 */

#define PI acos(-1.0)
#define E 1e-6
#define MOD 16007
#define INF 0x3f3f3f3f
#define N 1001
#define LL long long
using namespace std;
bool vis[N];
int link[N];
vector<int> G[N];
bool dfs(int x)
{
    for(int i=0;i<G[x].size();i++)    //将与x相连的点进行遍历
    {
        int y=G[x][i]; //y是跟x相连的第i个点
        if(!vis[y])    //如果y并没有被遍历过
        {
            vis[y]=true; //设y被标记过
            if(link[y]==-1 || dfs(link[y]))
            {
                link[y]=x; //将两者连在一起
                return true;
            }
        }
    }
    return false;
}
int hungarian(int n)
{
    int ans=0;
    for(int i=0;i<n;i++) //不断找增广路
    {
        memset(vis,false,sizeof(vis));  //在遍历每一个点的时候，将标记数组vis都设置为false
        if(dfs(i)) ans++;               //如果对i这个点进行dfs，它跟别的点连起来了，就是link更新了，则ans++。
    }
    return ans;
}
int main()
{
    int n,k; //n*n的表格，k个阻碍
    while(scanf("%d%d",&n,&k)!=EOF && (n+k))
    {
        memset(link,-1,sizeof(link));  //将link数组都设为-1
        for(int i=0;i<n;i++) G[i].clear();
        while(k--)                     //输入阻碍的坐标
        {
            int x,y;
            scanf("%d%d",&x,&y);
            G[x].push_back(y);         //将列跟行暂时连在一起（不是真的连在一起）
        }
        printf("%d\n",hungarian(n)); //n*n的表格
    }
    return 0;
}