欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分图性质及算法总结

程序员文章站 2022-05-22 15:39:02
...

二分图总结

定义

二分图是指对于一个图G=(V,E),若能将其点集分为两个互不相交的两个子集X、Y,
使得X∩Y=∅,且对于G的边集V,若其所有边的顶点全部一侧属于X,
一侧属于Y,则称图G为一个二分图。

清晰明了

匹配

对于一个二分图G的子图M,若M的边集E的的任意两条边都不连接同一个顶点,
则称M为G的一个匹配。

最大匹配就是最大化M

方法

1.匈牙利算法

时间复杂度\(O(nm)\)

先前面的和前面的匹配

如果后来的和前面发生冲突,先试着让后来的优先,然后递归匹配前面的,如果发现前面的没有匹配的了,就还原。

/*
@Date    : 2019-07-20 09:35:35
@Author  : Adscn ([email protected])
@Link    : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
    RG int xi=0;
    RG char ch=gc;
    bool f=0;
    while(ch<'0'|ch>'9')ch=='-'?f=1:f,ch=gc;
    while(ch>='0'&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
    return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
    if(k<0)k=-k,putchar('-');
    if(k>=10)pi(k/10,0);
    putchar(k%10+'0');
    if(ch)putchar(ch);
}
const int MAXN=1007;
const int MAXM=1e6+7;
struct edge{
    int v,nxt;
}e[MAXM];
int head[MAXN],cnt;
inline void add(int u,int v)
{
    e[++cnt]=(edge){v,head[u]};
    head[u]=cnt;
}
int n,m;
int match[MAXN],dfn[MAXN];
inline bool dfs(int p,int tim)
{
    for(int i=head[p],v=e[i].v;i;i=e[i].nxt,v=e[i].v)
    {
        if(dfn[v]==tim)continue;
        dfn[v]=tim;//被这一轮匹配了
        if(match[v]==0||dfs(match[v],tim))
        {
            match[v]=p;
            return true;
        }
    }
    return false;
}
int main(void)
{
    n=gi,m=gi;
    int e=gi;
    for(int i=1;i<=e;++i)
    {
        int u=gi,v=gi;
        if(u>n||v>m)continue;
        add(u,v);
    }
    int ans=0;
    for(int i=1;i<=n;++i)ans+=dfs(i,i);
    pi(ans);
    return 0;
}
2.最大流dinic

我们建立源点s,汇点t

将s到左点集连流量1的边,

左点集与右点集连流量1的边,

右点集连流量1的边到t

最大流量就是最大匹配。

正确性显然

时间复杂度

\(跑得贼快O(\text{跑得贼快})\)

/*
@Date    : 2019-07-20 10:15:01
@Author  : Adscn ([email protected])
@Link    : https://www.cnblogs.com/LLCSBlog
*/
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
    RG int xi=0;
    RG char ch=gc;
    bool f=0;
    while(ch<'0'|ch>'9')ch=='-'?f=1:f,ch=gc;
    while(ch>='0'&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
    return f?-xi:xi;
}
template<typename T>
IL void pi(T k,char ch=0)
{
    if(k<0)k=-k,putchar('-');
    if(k>=10)pi(k/10,0);
    putchar(k%10+'0');
    if(ch)putchar(ch);
}
const int MAXN=1007*2;
const int MAXM=1e6+7+MAXN;
const int inf=2147483647;
struct edge{
    int v,nxt,flow;
}e[MAXM<<1];
int head[MAXN],cnt;
int cur[MAXN];
inline void add(int u,int v,int f)
{
    e[cnt]=(edge){v,head[u],f};
    head[u]=cnt++;
}
inline void link(int u,int v,int f){add(u,v,f),add(v,u,0);}
int n,m;
int dep[MAXN];
int maxflow=0;
inline bool bfs(int s,int t)
{
    static int Q[MAXN],l,r;
    Q[l=r=0]=s;
    memset(dep,-1,sizeof dep);
    dep[s]=0;
    while(l<=r)
    {
        int p=Q[l++];
        for(int i=head[p];~i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(dep[v]==-1&&e[i].flow)
            {
                dep[v]=dep[p]+1;
                Q[++r]=v;
            }
        }
    }
    return ~dep[t];
}
inline int dfs(int p,int t,int restflow)
{
    if(p==t||restflow==0)return restflow;
    int sumflow=0;
    for(int &i=cur[p],flow;~i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(e[i].flow&&dep[v]==dep[p]+1&&(flow=dfs(v,t,min(restflow,e[i].flow))))
        {
            restflow-=flow,sumflow+=flow;
            e[i].flow-=flow,e[i^1].flow+=flow;
            if(restflow==0)break;
        }
    }
    return sumflow;
}
inline void dinic(int s,int t)
{
    while(bfs(s,t))
        memcpy(cur,head,sizeof head),maxflow+=dfs(s,t,inf);
}
int main(void)
{
    n=gi,m=gi;
    memset(head,-1,sizeof head);
    int e=gi;
    for(int i=1;i<=e;++i)
    {
        int u=gi,v=gi;
        if(u>n||v>m)continue;
        link(u,v+n,1);
    }
    int s=0,t=n+m+1;
    for(int i=1;i<=n;++i)link(s,i,1);
    for(int i=1;i<=m;++i)link(i+n,t,1);
    dinic(s,t);
    pi(maxflow);
    return 0;
}

判定

模板题NOIP2010关押罪犯


定理:

一个无向图是二分图,当且仅当图中不存在奇环


要判定非常简单,利用性质染色就可以了。

对于所有连通块,将相邻顶点染成不同颜色,如果已经是同色的就一定不是二分图。

代码略。

时间复杂度\(O(n)\)

一些有用的性质

最小点覆盖:取最少的点覆盖所有的边。

最小边覆盖:取最少的边覆盖所有的点

1.二分图中最小点覆盖等于最大匹配

证明显然

2.二分图中最小边覆盖等于顶点数-最大匹配

考虑给没被最大匹配的边匹配的点弄个虚拟点匹配上

然后我们最小边覆盖等于现在所有的匹配边的个数。

这个等于最大匹配+没匹配的点。

顶点数=最大匹配*2+没匹配的点。

所以,最小边覆盖=顶点数-最大匹配。

上一篇: 最大矩形

下一篇: 二分算法总结