二分图板子

①二分图的定义与判定

I.二分图:设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)并且图中的每条边（i，j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j inB)则称图G为二分图. 以上是度娘对二分图的定义,其实我认为太过正规的定义反而不便于理解,不如直接理解对二分图的判定,自然会理解二分图的定义.

II.判定: 用dfs对图进行黑白染色,当这个点染成黑色时,那与这个点相邻的点染成白色,否则反之.当对所有点进行黑白染色,都未发生逻辑冲突(本来一个点是黑色,但又要它染成白色),那我们成功的将图上所有点分成黑白两个集合,就是上文的集合A,B.可以试着做LGP1330,加深对二分图判断的理解,贴上此题代码.

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 #define e exit(0)
 5 #define R register
 6 int n,m,from,to,cnt,flag,id,ans,head[10010],vis[10010],color[10010],check[10010];
 7 struct bian{
 8     int to,next;
 9 }len[200010];
10 void add(int from,int to)
11 {
12     len[++cnt].to=to;
13     len[cnt].next=head[from];
14     head[from]=cnt;
15 }
16 void dfs(int x,int fa,int co)
17 {
18     if(flag)
19         return;
20     color[x]=co;
21     for(R int k=head[x];k;k=len[k].next)
22     {
23         int to=len[k].to,nowco;
24         if(to==fa) continue;
25         if(co==1) nowco=2;
26         else nowco=1;
27         if(color[to]&&color[to]!=nowco)
28         {
29             flag=1;
30             return;
31         }
32         dfs(to,x,nowco);
33     }
34     if(x==id){
35         int sum1=0,sum2=0;
36         for(R int i=1;i<=n;++i){
37             if(!vis[i]||check[i]) continue;
38             if(color[i]==1){
39                 ++sum1;
40                 check[i]=1;
41             }
42             else if(color[i]==2){
43                 ++sum2;
44                 check[i]=1;
45             }
46         }
47         ans+=min(sum1,sum2);
48     }
49 }
50 int main()
51 {
52 //    freopen("s.in","r",stdin);
53 //    freopen("s.out","w",stdout);
54     scanf("%d%d",&n,&m);
55     for(R int i=1;i<=m;++i)
56     {
57         scanf("%d%d",&from,&to);
58         add(from,to),add(to,from);
59         vis[from]=vis[to]=1;
60     }
61     for(R int i=1;i<=n;++i)
62         if(vis[i]==1&&color[i]==0)
63         {
64             id=i;
65             dfs(i,i,1);
66         }
67     if(flag){
68         printf("Impossible");
69         return 0;    
70     }
71     printf("%d",ans);
72     return 0;
73 }

②二分图的最大匹配.

I.定义:对与二分图同一集合没有边相连,但同一集合的点不能连向另一个集合的同一个点,现在我们进行连边操作,问满足要求前提,我们能连多少条边?

II.方法: 其实求增广路的方法就是一个贪心策略.match数组表示这个点于哪条边相匹配,vis数组表示我们在这一次匹配当中点是否访问过.匹配的过程就是一个贪心的过程,当我们对于一个点匹配时,发现这个点所连的点没有被匹配过就就直接匹配,返回true表示匹配成功,若这个点匹配过我们就对已经匹配这个点的点进行重新匹配,希望找到一个同的点匹配成功,这样我们会得到一条连边 ,匹配失败就换点,要知道每一匹配的子过程都是这样走的,可看做一贪心的协调.vis表示我们在这次匹配中已经访问过了,不论是匹配成功还是失败,它已经进行过贪心,强行将它再拉入这次匹配不会再得到更优匹配.以LG3386为例,上code.

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define R register
int n,m,e,ans,check[2010][2010],vis[2010],match[2010];
bool dfs(int x)
{
    for(R int j=n + 1;j<=m + n;++j){
        if(!check[x][j]||vis[j]) continue;
        vis[j]=1;
        if(!match[j]||dfs(match[j]))
        {
            match[j]=x;
            match[x]=j;
            return true;
        }
    }
    return false;
}
int main()
{
//    freopen("s.in","r",stdin);
//    freopen("s.out","w",stdout);
    scanf("%d%d%d",&n,&m,&e);
    for(R int i=1;i<=e;++i){
        int from,to;
        scanf("%d%d",&from,&to);
        to += n;
        check[from][to]=1;
    }
    memset(match,0,sizeof(match));
    for(R int i=1;i<=n;++i)
    {
        memset(vis,0,sizeof(vis));
        if(!match[i]&&dfs(i))
            ++ans;
    }
    printf("%d",ans);
    return 0;
}