知识兔

[二分图初步]【模板】二分图匹配

30

题目链接

题目简述:就是二分图板子。

Q:什么是二分图呢?

A:二分图就是一个无向图可以分成两个子集,且满足这个图中每条边的端点都是属于不同子集的。

什么意思呢?上面这个看起来好像有点晦涩难懂,其实这个可以很好地用生活来解释。在现实生活中,每个班级都有那么几对“关系异常”的男女。我们将整个年级中所有这样的人拉出来站在一起,如果发现没有一对是同性的(笑),那么就说明这是一群符合大众道德观(我不歧视同性恋)的早恋学生,那么可以说这群人是符合二分图的定义的。这相当于所有人是一个图,他们之间的情愫就是将他们相连的边,不同的性别为不同的子集,两个子集不相交(双性人太草),且每条边连接着的端点不在同一个子集(如果在的话就有同性恋啦)。

了解了二分图的定义之后,那么二分图会发生那些有趣的事情呢?我们还是依靠上面的模型。首先定义一个词:匹配,也可以称作某条边和它连着的两个点的合称。在这个模型中就相当于是一对情侣的意思。一个图里可以有很多个匹配,就跟一个年级里可能有很多对情侣是一样的(不要早恋!),那么一个图中的匹配满足互不相交的性质,匹配的数量最多的情况叫做最大匹配。这个解释起来也很简单,在把情侣们拉出来后,我们会发现有些渣男/女,与他们相恋的可能有两个或者多个(太草了),这时候大家醋意勃发,要求这些人立刻做出决定终生的选择,也就是相互确立关系,成为匹配。匹配不相交也就是因为都决定终生了就不允许存在三角关系了。

那么为了使这些学生能够得到幸福(早恋是得不到幸福的!),我们就要找到最大子集。那怎么办呢?我们这个时候需要用到一个算法-匈牙利算法。

我们引进一个定义:增广路。但是由于很复杂(有兴趣的自己查),我就直接作出感性的解释。首先我们有着一些标记:与某人确定关系的,以及某人是否正在调换过程中。以下的解释均由男孩子来选女孩子(反过来也是一样的),首先,对于一个男生,他要开始选了,他就找啊找,那么遇到的有两种情况:1.找的女生已经有选择了 2.还没选择。1的话我们要为自己的幸福争取一些机会,于是尝试着请求以下让别人换一个男朋友,那么此时就问男同胞,你能不能再找一个?(此时这个女生已经在调换过程中了,所以男同胞不能再找她),如果能换(函数返回值为一),那么争取到了这一个幸福(横刀夺爱太草),然后你我关系确认一下(户口簿改名字?),再返回1(因为有可能是别人让我换一个,要给别人一个答复),换不了就只有找其他人了。2就直接选就好了(毕竟还能再换)。

那么算法部分已经结束了,要注意一个点:当这个函数不是被自己调用而是主函数调用的时(也就是不是别人让我换,而是我自己要找),一定要清零标记数组!(即是否在调换过程的标记),并且这个标记只标记被选择的哪一方就行了。(要问为什么的话就是这个数组的作用就在于不让男孩子找迷糊了,给他指出哪些是碰不得的,因为别人正等着换)

代码

#include<iostream>
#include<cstdio>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
    char ch;
    int res=0,f=1;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        res=res*10+(ch-'0');
        ch=getchar();
    }
    return res*f;
}
const int MAXN=20005;
int n,m,e,u,v,ans;
bool is_to[MAXN][MAXN],vis[MAXN];
int l[MAXN],r[MAXN];
bool dfs(int x){
    for(int i=1;i<=m;++i){
        if(!vis[i]&&is_to[x][i]){
            vis[i]=1;
            if(!r[i]||dfs(r[i])){
                r[i]=x;
                l[x]=i;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    n=read();m=read();e=read();
    for(int i=1;i<=e;++i){
        u=read();v=read();
        if(u<=n&&v<=m)is_to[u][v]=1;
    }
    for(int i=1;i<=n;++i)if(!l[i]){
        memset(vis,0,sizeof(vis));
        ans+=dfs(i);
    }
    cout<<ans;
    return 0;
}
知识兔View Code

匈牙利算法就是DFS的部分啦。

计算机