二分图最大匹配

二分图最大匹配 是网络流的一个简化。二分图的点可以分为两部分,每边的点之间没有边连接。对于二分图匹配的匈牙利算法,有两种理解:请参见Renfei Song’s BlogDark Scope的CSDN博客。

我就是靠这两篇博文入门的,他们已经讲解的十分详尽、清楚了。看完第二篇博客才开始有点理解,发现做出来的效果竟然是和第一篇博客一样的!

但是我还是只能大概仿照他们的代码,写了一个二分图匹配的题:CodeVS2776

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
vector<int>club[210];//这个是储存社团中的学生的。使用了动态数组,因为不想浪费空间,也不知道具体有多少个学生。
bool vis[210];//在每次寻找增广路的时候是否已经寻找过
int linker[210];//学生代表的社团,-1表示还没有代表社团
bool dfs(int asso){
    for(int i=0;i<club[asso].size();i++){
        if(!vis[club[asso][i]]){
            vis[club[asso][i]]=true;
            if(linker[club[asso][i]]==-1||dfs(linker[club[asso][i]])){
                //这里可以理解为当前社团想选的代表 代表的社团 可以让位
                //也可以理解为寻找一条增广路
                linker[club[asso][i]]=asso;
                //寻找到一条增广路之后,把增广路上面不是匹配边的边改为匹配边,
                //是匹配边的改为非匹配边
                return true;
            }
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(linker,-1,sizeof(linker));
    int n,m,stu,cnt=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        while(cin>>stu,stu!=0){
            club[i].push_back(stu);
        }
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i)){//存在增广路,则会多一条匹配边
            cnt++;
        }
    }
    cout<<cnt;
}

很快就会真正开始深入探究网络流,到那时还可以返回来再看看二分匹配的应用。

avatar
Kerry Su