LOADING

加载过慢请开启缓存 浏览器默认开启

二分图最大匹配

判断二分图
寻找最大匹配

最近学点图论,总不能暑假啥都没学。

所谓二分图,就是对于左右两个集合,每个集合内的任意两点不连边,边只连接两个不同集合内的分别一点,如图(A集合有{1,2,3,4},B集合{1,2,3,4},两个集合的数量和元素都不需要相同)


以上的边练成的路径为A(1)→B(2),A(2)→B(1),这是二分图的一种成立条件,即单边无环,但还存在有环的情况,如下

此时的环为A(1)→B(2)→A(3)→B(3)→A(1),此时环内一共有四个元素,可以可以证明的是,若当环内元素为奇数个时,该图必然不为二分图,

若环内元素有奇数个时,?的位置必然为A,此时A→A与二分图定义矛盾,所以二分图内的环必为偶数环。

对于给定的一个带连边的图,可以用染色法判定二分图,

思路:我们可以把两个不同的集合中的元素染色为1和2。

遍历A中的每一个点,若该点未被染色,则染为1,然后顺着与该点相连的点,将其染为相反的颜色,若过程中发现有下一个点的颜色与当前点的颜色相同,则该图不是二分图。

#include<bits/stdc++.h>
using namespace std;
int const N=2e5+10;
int h[N],ne[N],w[N],cnt=0;
int color[N];
void add(int a,int b){  //数组存连接点 ,和最短路存路径的方法相同
    w[++cnt]=b,ne[cnt]=h[a],h[a]=cnt;
}
bool dfs(int x,int u){
    color[x]=u;
    for(int i=h[x];i!=-1;i=ne[i]){  //查找与该点相连的一条路到底
        int j=w[i];
        if(!color[j]){   //用3-u来表示相反的颜色
           if(!dfs(j,3-u))return false;
        }
        else if(color[j]==u)return false;
           //邻接点的颜色与当前点颜色相同,跳出
    }
    return true;
}
int main()
{
    int n,m,k=1;cin>>n>>m;
    memset(h,-1,sizeof h);
    while (m -- ){
        int a,b;cin>>a>>b;
        add(a,b);add(b,a);  //因为dfs的时候一条路到底,所以相反的路径也要加
    }
    for(int i=1;i<=n;++i){
        if(!color[i]){  //该点已经被染色
            if(!dfs(i,1)){  //染色失败,不为二分图
                k=0;
                break;
            }
        }
    }
    if(k)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

ok,二分图判断完毕,开始匹配问题

上题:

P3386 【模板】二分图最大匹配 - 洛谷 | 计算机科学教育新生态

所谓的匹配:就是在二分图中每个集合的元素只能连一条边,这两个元素的连接就是匹配。

最大匹配:在一个二分图中存在最多的匹配数量

完全匹配:两个集合中的全部元素都能匹配上


匈牙利算法可以帮助解决这个问题

如图绿线表示两点有连接,按遍历A集合的顺序来,我们先看A中点1,发现A(1)可以与B(2)连,就连这俩

然后看A2的时候发现A2可以和B2连,也就连接他们

然后到A3的时候,发现A3的第一个连接点B1已经被连了,这就是所谓的增广路了,一点被多个点所连接,这时候我们需要查看B1所连接的点有没有另外的连接点,发现A1还连接着B2,但B2被A2连接了,我们又看A2还另外连B3,而B3没有被连,那么我们就将A2连B3,于是A1就可以连B2,A3可以连B1了,知识点很少,挺容易看懂的

#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define per(i,n,m) for(int i=n;i>=m;--i)
#define PII pair<int,int>
#define INF 1<<30
using namespace std;
typedef long long ll;
const int N=2e3+10;
bool link[N][N];
int p[N],st[N],n,m,e,ans=0;
//p【i】=j  表示第二个集合中的i点和第一个集合中的j点匹配
bool dfs(int x){
    rep(i,1,m){
        if(link[x][i]&&!st[i]){   //如果该点和x点有连接,并且此时i点还没被用过
           st[i]=1;
           if(p[i]==0||dfs(p[i])){  //i点没有匹配的边,或者i点所匹配的边还有另外的匹配
               p[i]=x;   //更新i的匹配点是x
               return 1;
           }
        }
    }
    return 0;
}
 
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>e;
    while(e--){
        int x,y;cin>>x>>y;
        link[x][y]=1;   //x点和y点有连接
    }
    rep(i,1,n){  //遍历第一个集合
        memset(st,0,sizeof st);
        if(dfs(i))ans++;  //如果该点匹配成功
    }
    cout<<ans;
    return 0;
}