今天本来想整理
在
让我们回到第一个情景：国家主席布里jiojio邓布利多先生对于相亲大会的成果并不满意，在你向他说明情况后，他决定修改本国宪法
：“其实吧，\(5\)号人也挺好的。”然后\(3\)号去找\(5\)号，发现\(5\)号没有男朋友，于是\(3\)号和\(5\)号匹配，把\(1\)号让了出来
因为\(1\)号被\(3\)号让了出来，所以\(4\)号和\(1\)号成功匹配
最后一个男嘉宾\(6\)号：“我喜欢\(1\)号！”于是你们去找\(1\)号，\(1\)号有男朋友是\(4\)号
老套路，你去问\(4\)号能不能换，把\(1\)号让出来给\(6\)号，可是\(4\)号除了和\(1\)号之外没有边了，他说：“不换不换！老子不换！说什么也不换！”
然而\(6\)号也只喜欢\(1\)号，但是因为先到先得，你只能遗憾的告诉\(6\)号他得孤独终老了
现在笔者告诉你，刚才你所完成的，就是匈牙利算法的全过程了，这张二分图的最大匹配数就是\(3\)
这里写代码的时候注意如果遇到更换的情况，新换的那个点不可以是需要让出来的那个点
对于以上繁杂的过程，笔者用了一个更加违反人类伦理的话来总结：
好啦不扯皮了，相信经过笔者的一通比喻，大家已经明白了匈牙利算法的实现原理了，下面来看代码吧！
这里假设我们已经对二分图染好色并存在了\(col\)数组里
bool dfs(const int x){
//match[i]存右边i号点的匹配是左边的哪个点
for(unsigned int i=0;i<v[x].size();i++){//扫描x的所有出边
int y=v[x][i];
if(vis[y]==0){//如果扫描到的这个点不是需要让出来的那个点
vis[y]=1;//标记y点不能被需要更换的情况作为替换点
if(match[y]==-1||dfs(match[y])){ //match[y]==-1说明这个右边点没有匹配过，dfs(match[y])如果为真说明可以换
match[y]=x;//现在y和x匹配
return true;//返回真
}
}
}
return false;//如果不满足上面那一大串的条件，说明换不了，返回假
}
inline int APath(){//尝试匹配
int res=0;
for(int u=0;u<n;u++){//对于所有的点，我们只需要对黑点或白点尝试匹配即可
memset(vis,0,sizeof(vis));
if(col[u]==0){//如果是黑点就尝试匹配
if(dfs(u)) res++;//匹配成功
}
}
return res;//返回值为最大匹配数
}
Part 4：例题
学了这么牛B（哲学）的算法，怎么能不拿出来练练手呢？
传送门：https://www.luogu.com.cn/problem/P6268
题目中给出了\(m\)条边，被边连接的两个点种只能选一个，求最多选几个点
很容易就看出来本题是求最大独立集的一道题目，由于题目中给出的只是边连接的两个点，并不知道左还是右，所以我们要先染色
染好色后（本题的数据保证是二分图了，所以不用特判）我们直接跑一遍匈牙利，然后\(n-\)最大匹配数即可
然而交上去只有\(60\)分，不知所措的我\(De\)了一下午\(bug\)，然并卵（不让下数据蛋疼），最后愤怒的我抄了个题解下来去对拍
发现：我在记录右部节点的匹配点时，默认\(match[y]==0\)是没有匹配，但是，\(TND\)这个题有个\(0\)号点，如果\(0\)号点已经和\(y\)匹配上了，查询的时候还是默认\(y\)没有匹配过，导致找到了错的增广路，然后发现匹配数比真实的答案要大\(1\)，然后\(WA\)掉了……
所以为了避免类似的惨剧发生，这里强烈建议大家把\(match\)初始化成\(-1\)，避免踩坑
\(Code\)
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#include<map>
#include<utility>
#include<iostream>
#include<list>
#include<ctime>
#include<cmath>
#include<cstdlib>
#include<iomanip>
typedef long long int ll;
inline int read(){
int fh=1,x=0;
char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') fh=-1;ch=getchar(); }
while('0'<=ch&&ch<='9'){ x=(x<<3)+(x<<1)+ch-'0';ch=getchar(); }
return fh*x;
}
inline int _abs(const int x){ return x>=0?x:-x; }
inline int _max(const int x,const int y){ return x>=y?x:y; }
inline int _min(const int x,const int y){ return x<=y?x:y; }
inline int _gcd(const int x,const int y){ return y?_gcd(y,x%y):x; }
inline int _lcm(const int x,const int y){ return x*y/_gcd(x,y); }
const int maxn=5005;
std::vector<int>v[maxn];
int match[maxn],m,n,col[maxn];//col存每个点的颜色
bool vis[maxn];
bool dfs(const int x){
for(unsigned int i=0;i<v[x].size();i++){
int y=v[x][i];
if(vis[y]==0){
vis[y]=1;
if(match[y]==-1||dfs(match[y])){
match[y]=x;
return true;
}
}
}
return false;
}
inline int APath(){//求增广路
int res=0;
for(int u=0;u<n;u++){
memset(vis,0,sizeof(vis));
if(col[u]==0){//如果是黑点就寻找增广路
if(dfs(u))res++;//匹配成功
}
}
return res;
}
void paint(const int x,const int color){
int y;
col[x]=color;
for(unsigned int i=0;i<v[x].size();i++){
if(col[y=v[x][i]]==-1){//没有被染色
if(color==0) paint(y,1);//1表示白色
else paint(y,0);//0表示黑色
}
}
}
int main(){
// freopen("data.in","r",stdin);
// freopen("sol.out","w",stdout);
memset(match,-1,sizeof(match));
n=read(),m=read();
for(int i=0,x,y;i<m;i++){
x=read(),y=read();
if(x==y) continue;
v[x].push_back(y);
v[y].push_back(x);
}
memset(col,-1,sizeof(col));//一开始都没有被染色
for(int i=0;i<n;i++)
if(col[i]==-1) paint(i,0);//如果没有被染色，默认为黑色
int path=APath();
printf("%d\n",n-path);
return 0;
}
好了今天关于二分图和增广路的分享就到这里了，感谢您的阅读，如果觉得笔者写的不错的话，请高抬贵手来个三连，谢谢您的支持！！！