您的位置: 首页  >  IT文章  >  二分图知识点温习

二分图知识点温习

分类: IT文章 • 2024-03-20 16:37:06

二分图

定义：顾名思义就是将整个图分为两个部分的图。这里我们将点分成两个集合，A,B并且规定，任意同一个集合里的点没有直接相连的边，也就是说所有的点都是从A集合里的一个点连向B集合里的一个点。这样的图叫做二分图。

判定：那么如何判定一个图是不是二分图呢？先给出定理：当一个图为二分图是，当且仅当这个图中没有奇环(点的个数为奇数的环).对于这个定理的证明，不详解释了。（其实是因为我不懂....）但我们可以从构造的角度了解这个定理。二分图不是要求两个点集吗，那我们就尝试将一个图给划分成一个二分图。首先我们可以先对非环上的点进行划分，他们最多是一个数，我们定义一个点权为1和2，分别代表两个集合。依次将所有的点给成1和2，也就是将所有1的点邻近节点给成2，这样因为没有环的存在，一定是合法的。接下来考虑环的情况，注意我们这里只考虑最简单环的情况（即纯粹是一个环不含其余多余的节点），若环的长度为偶数，我们发现这样染色并没有什么冲突，但若环的长度为奇数，那么一定会有冲突，这也就是二分图与奇环格格不入的原因了。

最大匹配：对于一个二分图中的一个边集，若任意两条边都没有公共点的话，则成为这是二分图的一组匹配，边的数量最多的一组匹配被称为最大匹配。

匈牙利算法：

inline bool dfs(int x)
{
    for(register int i=link[x];i;i=a[i].next)
    {
        int y=a[i].y;
        if(vis[y]!=id)
        {
            vis[y]=id;
            if(!match[y]||dfs(match[y])) 
            {
                match[y]=x;return true;
            }
        }
    }
    return false;
}

for(int i=1;i<=n;++i)
{
    id++;
    if(dfs(i)) ans++;
}
View Code

这里对于右部节点只能便利一次的理解：首先我们要明确我们加入匹配的点不会因为我们将其换点而失去匹配，也就是说我们每次找新的匹配都是将未加入匹配的点加入其中，若某次右边的点访问过，若其左部匹配的点同意更换则直接结束，若不同意则说明其左部匹配的点在未加入匹配的点钟找不到新的匹配，所以在当前这个点(代码中的i)找新匹配时其左部匹配的点不同意，则会一直都不同意。这样理解即可。

 最大带权匹配 ：若二分图中的边带有权值，要求找到最大匹配的同时要求所有边的全职和也最大。

KM算法是个非常有优秀的算法，对于稠密图的情况，复杂度比网络流更优秀。

KM算法详解：

//右边点的匹配点.左边点，右边点是否使用.时间戳,左边点，右边点的顶标.
inline bool find(int x)
{
    usex[x]=id;//x已使用 
    for(int i=1;i<=n;++i)//枚举每一个右边的点. 
    {
        if(usey[i]!=id&&cx[x]+cy[i]==w[x][i])//如果右边点未使用并且符合期望的规则. 
        {
            usey[i]=id;                        //右边点i已使用. 
            if(!match[i]||find(match[i])) {match[i]=x;return true;} 
        }//若i未匹配或者i的匹配点能换点。 
    }
    return false;
}

inline int KM()
{
    for(int i=1;i<=n;++i)//枚举每个左边的点。 
    {
        while(1)   
        {
            id++;   //更新时间戳。      
            int d=qwq;//方便更新需要改的最小期望。 
            if(find(i)) break; //如果能为i找到匹配，则不需要改期望，直接找下一个点。 
            for(int j=1;j<=n;++j) if(usex[j]==id)  //否则，找到所有使用过的左边点 
                for(int k=1;k<=n;++k) if(usey[k]!=id)//所有未被用的右边点 
                    d=min(d,cx[j]+cy[k]-w[j][k]);  //更新需要改的最小期望. 
            for(int j=1;j<=n;++j) if(usex[j]==id) cx[j]-=d; //更新左边的顶标 
            for(int j=1;j<=n;++j) if(usey[j]==id) cy[j]+=d;    //更新右边的顶标.    
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i) ans+=w[match[i]][i];//累加答案. 
    return ans;
}
View Code

 这是没优化过的版本，严格的复杂度是O(n^4),随机数能跑到O(n^3),牛客中写了一道题这样写的话T到飞起，下还有一个优化过的代码，用bfs代替dfs，并且每次记录增光路的路径，复杂度最坏情况下卡到O(n^3).

queue<int>q;//bfs所需队列 
bool vx[N],vy[N];//标记左边点和右边点是否用过 
int cx[N],cy[N];//左边点和右边点的顶标值。
int px[N],py[N];//最后确定的左右两边匹配的点
int pre[N];//每次寻找增光路时记录的路径 


inline void aug(int v)//更新路径 
{
    int t;
    while(v)
    {
        t=px[pre[v]];//预存下pre[v]原本匹配的点 
        py[v]=pre[v];// v与pre[v]相互匹配 
        px[pre[v]]=v;
        v=t;//向下一个点继续更新。 
    }
}
inline void bfs(int s)
{
    memset(vx,0,sizeof(vx));
    memset(vy,0,sizeof(vy));//初始化每个点是否用过，并且将右边每个点的松弛值设成INF 
    fill(slack+1,slack+n+1,INF);    
    while(!q.empty()) q.pop();//清空队列。 
    q.push(s);//以s为起点进行增广。 
    while(1)
    {
        while(!q.empty())//进行一次增光路的探寻 
        {
            int x=q.front();q.pop(); 
            vx[x]=1;//取出左边点 
            for(int i=1;i<=n;++i) if(!vy[i])//寻找未使用的右边点 
            {
                if(cx[x]+cy[i]-w[x][i]<slack[i])//更新其松弛值 
                {
                    slack[i]=cx[x]+cy[i]-w[x][i];
                    pre[i]=x;//标记路径 
                    if(slcak[i]==0)//当前边为合法的。 
                    {
                        vy[i]=1;//标记其使用过 
                        if(!py[i]) {aug(i);return;}//当前点为匹配，直接用，更新路径 
                        else q.push(py[i]);//否则继续往下找 
                    }
                }
            }
        }
        int d=INF;
        for(int i=1;i<=n;++i) if(!vy[i]) d=min(d,slack[i]);//找右边未用过的点进行松弛 
        for(int i=1;i<=n;++i)
        {
            if(vx[i]) cx[i]-=d;//左边用过的减 
            if(vy[i]) cy[i]+=d;//右边用过的加 
            else slack[i]-=d;//右边没用过得减。 
        }
0        for(int i=1;i<=n;++i) if(!vy[i]) // 右边未用过的点 
        {
            if(slack[i]==0)//将当前可加入增光路的右边点加进去。 
            {
                vy[i]=1;
                if(!py[i]) {aug(i);return;}
                else q.push(py[i]);
            }
        }
    }
}
‘ 
int main()
{
    for(int i=1;i<=n;++i) bfs(i);//对左边每个点进行增广。 
}
View Code

相关推荐