二分匹配 ---- 匈牙利算法

这个算法真心很精妙，其实代码很简单，但是理解其中的奥秘还真要花点时间

matrix67大牛说的好：说穿了，就是你从二分图中找出一条路径来，让路径的起点和终点都是还没有匹配过的点，并且路径经过的连线是一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现。找到这样的路径后，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。详见：二分图最大匹配问题匈牙利算法

其实原理还就是这样，所以，我们采用递归就很容易找出交错轨.

USACO section 4.2 就有这样一个题目 我给出源码，很精妙啊  题目位置：The Perfect Stall

/*
ID: wangxua4
PROG: stall4 
LANG: C++
*/
//usaco 4.2 stall4    最大二分匹配 匈牙利算法
#include <cstdio>
#include <cstring>
int n,m,g[201][201],link[201];
bool f[201];

bool find(int i)
{
    for(int j = 1;j <= m;j++)
    {
        if(g[i][j] == 1 && !f[j])
        {
            f[j] = true;
            if(link[j] == 0 || find(link[j]))//精妙之处！！
            {
                link[j] = i;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    freopen("stall4.in","r",stdin);
    freopen("stall4.out","w",stdout);
    scanf("%d%d",&n,&m);
    int ans = 0,i,j,k,_k;
    for(i = 1;i <= n;i++)
    {
        scanf("%d",&k);
        for(j = 1;j <= k;j++)
        {
            scanf("%d",&_k);
            g[i][_k] = 1;
        }
    }
    for(i = 1;i <= n;i++)
    {
        memset(f,0,sizeof f);
        if(find(i))++ans;
    }
    printf("%d\n",ans);
    return 0;
}