二分圖的染色與比對

二分圖：圖中點集可分成兩部分,使處于同一部分的點間沒有連邊

染色法,是一種簡單地判斷是否為二分圖的方法.

對圖中的每個點進行染色,使相臨的點顔色不同,如果可以完成則為二分圖,否則不為.

BFS實作：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
int n,m,ru,rv,tot;
int first[],nxt[],color[];
bool flag;
struct edge
{
    int u,v;
}l[];
queue<int>q;
void build(int f,int t)
{
    l[++tot]=(edge){f,t};
    nxt[tot]=first[f];
    first[f]=tot;
}
int bfs(int s)
{
    q.push(s);
    color[s]=;
    while(!q.empty())
    {
        int k=q.front();
        q.pop();
        for(int i=first[k];i!=-;i=nxt[i])
        {
            int x=l[i].v;
            if(color[x]==-)
            {
                q.push(x);
                color[x]=color[k]^;//color[x]=!color[k];
            }
            if(color[x]==color[k])
            return ;
        }
    }
    return ;
}
int main()
{
    memset(first,-,sizeof(first));
    memset(color,-,sizeof(color));
    scanf("%d%d",&n,&m);
    for(int i=;i<=m;i++)
    {
        scanf("%d%d",&ru,&rv);
        build(ru,rv);
        build(rv,ru);
    }
    for(int i=;i<=n;i++)//周遊每一個點 
    {
        if(color[i]==-&&first[i]!=-)//若起始點沒有染過色(此點及此點可到達的點未被染色)并且起始點有出邊 
        {
            if(!bfs(i))
            flag=;
        }
    }
    if(flag==)
    printf("NO");
    else printf("YES");
    return ;
}
           

DFS實作：

http://acm.hdu.edu.cn/showproblem.php?pid=5285 wyh2000 and pupil

poor wyh…

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,ru,rv,tot,zero,one,t,ans1,ans2;
int first[],nxt[],color[];
bool flag;
struct edge
{
    int u,v;
}l[];
void build(int f,int t)
{
    l[++tot]=(edge){f,t};
    nxt[tot]=first[f];
    first[f]=tot;
}
void dfs(int s)
{
    for(int i=first[s];i!=-;i=nxt[i])
    {
        int x=l[i].v;
        if(color[x]==color[s])
        flag=;
        if(color[x]!=-)
        continue;
        if(color[x]==-)
        {
            color[x]=color[s]^;
            if(color[x]==)
            one++;
            else zero++;
        }
        dfs(x);
    }
}
int main()
{
    scanf("%d",&t);
    for(int i=;i<=t;i++)
    {
        tot=;
        memset(first,-,sizeof(first));
        memset(color,-,sizeof(color));
        scanf("%d%d",&n,&m);
        if(n<=)
        {    
            printf("Poor wyh\n");    
            continue;    
        }    
        if(m==)
        {    
            printf("%d 1\n",n-);    
            continue;    
        }   
        for(int i=;i<=m;i++)
        {
            scanf("%d%d",&ru,&rv);
            build(ru,rv);
            build(rv,ru);
        }
        ans1=ans2=flag=;
        for(int i=;i<=n;i++)
        {
            if(color[i]==-&&first[i]!=-)
            {
                one=;
                zero=;
                color[i]=;
                dfs(i);
                ans1+=max(one,zero);
                ans2+=min(one,zero);
            }
            if(color[i]==-&&first[i]==-)
            ans1++; 
        }
        if(flag==)
        printf("Poor wyh\n");
        else printf("%d %d\n",ans1,ans2);
    }
    return ;
}
           

二分圖比對算法：匈牙利算法

https://www.luogu.org/problem/show?pid=3386 二分圖比對模闆

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,e,ru,rv,ans,tot;
int x[],y[],first[],nxt[];
bool vis[];
struct edge
{
    int u,v;
}l[];
void build(int f,int t)
{
    l[++tot]=(edge){f,t};
    nxt[tot]=first[f];
    first[f]=tot;
}
int path(int k)
{
    for(int i=first[k];i;i=nxt[i])
    {
        int t=l[i].v;
        if(!vis[t])
        {
            vis[t]=;
            if(!y[t]||path(y[t]))//若t沒有比對或與t比對的點y[t]可以尋找一條增廣路與其他的點進行比對 
            {
                x[k]=t;//比對 
                y[t]=k;
                return ;
            }
        }
    }
    return ;
}
int main()
{
    scanf("%d%d%d",&n,&m,&e);
    for(int i=;i<=e;i++)
    {
        scanf("%d%d",&ru,&rv);
        if(ru>n||rv>m)//洛谷資料有誤...
        continue;
        build(ru,rv);
    }
    for(int i=;i<=n;i++)
    {
        if(!x[i])
        {
            memset(vis,,sizeof(vis));
            ans+=path(i);//統計比對數 
        }
    }
    printf("%d",ans);
    return ;
}
二分圖的最小頂點覆寫數=二分圖的最大比對數
二分圖的最小路徑覆寫數=點的數量-二分圖的最大比對數
二分圖的最小邊覆寫數=點的數量-二分圖的最大比對數
二分圖的最大獨立集大小=點的數量-二分圖的最大比對數
           

推薦部落格：http://www.cnblogs.com/shenben/p/5573788.html 對匈牙利算法進行詳盡的了解

推薦題目：http://codevs.cn/problem/1222/ 信與信封問題

先進行一次比對,再對比對的邊依次删除,如果不能完美比對,說明這條邊是不可或缺的,則将這條邊輸出

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,x,y,ans;
int lkx[],lky[],mp[][];
bool flag;
bool vis[];
int path(int k)
{
    for(int i=;i<=n;i++)
    {
        if(!mp[k][i]&&!vis[i])
        {
            vis[i]=;
            if(!lky[i]||path(lky[i]))
            {
                lkx[k]=i;
                lky[i]=k;
                return ;
            }
        }
    }
    return ;
}
int main()
{
    scanf("%d",&n);
    while()
    {
        scanf("%d%d",&x,&y);
        if(x==&&y==)
        break;
        mp[x][y]=;
    }
    for(int i=;i<=n;i++)
    {
        memset(vis,,sizeof(vis));
        if(path(i))
        ans++;
    }
    if(ans!=n)
    printf("none");
    else
    {
        for(int i=;i<=n;i++)
        {
            memset(vis,,sizeof(vis));
            int tmp=lkx[i];
            mp[i][tmp]=;
            lkx[i]=;
            lky[tmp]=;
            if(!path(i))
            {
                printf("%d %d\n",i,tmp);
                lkx[i]=tmp;
                lky[tmp]=i;
                flag=;         
            }
            mp[i][tmp]=;
        }
        if(!flag)
        printf("none");
    }
    return ;
}