二分图最大匹配的匈牙利算法

二分图又称作二部图，是图论中的一种特殊模型。

设G=(V,E)是一个无向图，如果顶点V可分割两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

 

解决二分图最大匹配的经典算法为匈牙利算法。算法的核心就是根据一个初始匹配不停的找增广路，直到没有增广路为止。

简单讲，增广路是一条交互道路，其中非匹配边与匹配边交替出现，并且起点与终点都没匹配。

如图：

 

上图中 红边 为已匹配的边， 黑边为没匹配，则图中的增广路有：

1) x5-> y5-> x4-> y4-> x3-> y2

2) x2-> y4-> x3-> y2

可以得出, 增广路有奇数条边，匹配边与非匹配边交替，顶点和终点未匹配，对于这样的增广路，我们可以通过将匹配边变成非匹配边，将非匹配边变成匹配边从而增加一条匹配

如： x5-> y5-> x4-> y4-> x3-> y2  经过变换后，变成如下图，增加了一条匹配边

这时图中已经没有了增广边，已经达到了最大匹配。另外可以证明，对于点 x , 如果求得了以 x 为起点的增广路径后，不管以后怎么改变，都将不会再有以 x 为起点的增广路径。

 

算法实现( POJ 1274 The Perfect Stall )

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

int const N= 250;
int match[N], flag[N], n, m;
vector<int> map[N];

int dfs( int u ){
    for( size_t i= 0; i< map[u].size(); ++i ){
        int v= map[u][i];
        int t= match[v];
        if( flag[v] ) continue;
        flag[v]= 1;
        
        if( t== -1 || dfs(t) ){
            match[v]= u;
            return 1; }
    }
    return 0;
}

int solve(){
    for( int i= 0; i<= m; ++i ) match[i]= -1;
    int ans= 0;
    for( int i= 1; i<= n; ++i ){
        for( int j= 1; j<= m; ++j ) flag[j]= 0;
        ans+= dfs(i);
    }
    return ans;
}
        

int main(){
    while( scanf("%d%d",&n,&m)!= EOF ){
        for( int i= 1; i<= n; ++i ){
            int num;
            scanf("%d",&num );
            for( int j= 0; j< num; ++j ){
                int x;
                scanf("%d",&x );
                map[i].push_back(x);
            }
        }
        printf("%d\n", solve() );
        for( int i= 0; i<= n; ++i ) map[i].clear();
    }
    
    return 0;
}