二分图

资料网址：http://www.cnblogs.com/kuangbin/category/315182.html （大神的二分题......Orz）

二分图——二分匹配之匈牙利算法

模板：

int g[MAXN][MAXN];
int uN,vN;
int linker[MAXN];
bool used[MAXN];
bool dfs(int u)
{
    int v;
    for(v=1;v<=vN;v++)    //右子集
        if(g[u][v]&&!used[v])      //左子集和右子集中的u,v有关系，并且右子集的这个元素未被访问
        {
            used[v]=true;       //标记
            if(linker[v]==-1||dfs(linker[v]))    //右子集的这个元素还没有被配对，或者能配对
            {
                linker[v]=u;    //与v配对的是u
                return true;
            }    
        }
    return false;    
}    
int hungary()
{
    int res=0,u;
    memset(linker,-1,sizeof(linker));
    for(u=1;u<=uN;u++)    //左子集
    {
        memset(used,0,sizeof(used));
        if(dfs(u))  
            res++;      //最大匹配的个数
    }  
    return res;  
}

用匈牙利算法可解决A,B,C

A COURSES POJ 1469 HDU1083

题意：有n种课,m个学生，每种课有几个学生参加，每个学生可以代表一种课，问是否每种课都有学生代表？ ————即问最大匹配关系是否=课程的种类

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <string.h>
 4 using namespace std;
 5 int n,m;
 6 int map[102][302],vist[302],c[302];
 7 int dfs(int k)
 8 {
 9     for(int i=1;i<=m;i++)
10         if(map[k][i] && !vist[i])
11         {
12             vist[i]=1;
13             if(c[i]==0 || dfs(c[i]))
14             {
15                 c[i]=k;
16                 return 1;
17             }
18         }
19         return 0;
20 }
21 int main()
22 {
23     int T;
24     scanf("%d",&T);
25     while(T--)
26     {
27         scanf("%d%d",&n,&m);    //n种课
28         memset(map,0,sizeof(map));
29         memset(c,0,sizeof(c));
30         int i,sum=0,a,b,j;
31         for(i=1;i<=n;i++)    //课的编号
32         {
33             scanf("%d",&b);
34             for(j=1;j<=b;j++)
35             {
36                 scanf("%d",&a);    //学生的编号
37                 map[i][a]=1;   //有关系
38             }
39         }
40         for(i=1;i<=n;i++)
41         {
42            memset(vist,0,sizeof(vist));
43            if(dfs(i))
44               sum++;
45         }
46         if(sum==n)
47             printf("YES
");
48         else
49             printf("NO
");
50     }
51 }

B Swap HDU 2819 题意：能否把对角线上都变成1？只能交换行或者列 ————即匈牙利算法判断能否达成，并记录过程

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int n,m;
int map[102][102],vist[102],c[102],a[102],b[102];
int dfs(int k)
{
    for(int i=1;i<=n;i++)
        if(map[k][i] && !vist[i])
        {
            vist[i]=1;
            if(c[i]==0 || dfs(c[i]))
            {
                c[i]=k;
                return 1;
            }
        }
        return 0;
}
int main()
{
    while(~scanf("%d",&n))
    {
        memset(map,0,sizeof(map));
        memset(c,0,sizeof(c));
        int i,sum=0,j;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                scanf("%d",&map[i][j]);
        for(i=1;i<=n;i++)
        {
           memset(vist,0,sizeof(vist));
           if(dfs(i))
              sum++;
        }
        if(sum<n)     //不能达到要求
        {
            printf("-1
");
            continue;
        }
        sum=0;
        for(i=1;i<=n;i++)
        {
            for(j=i;j<=n;j++)
                if(c[j]==i)
                    break;
            if(i!=j)     //不在对角线上
            {
                sum++;
                a[sum]=i;   //记录
                b[sum]=j;   //记录
                swap(c[i],c[j]);   //交换
            }
        }
        printf("%d
",sum);
        for(i=1;i<=sum;i++)
            printf("R %d %d
",a[i],b[i]);
    }
    return 0;
}

C Asteroids POJ 3041 匈牙利算法的运用题意：求最大匹配不解释

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <string.h>
 4 using namespace std;
 5 int n,m;
 6 int map[502][502],vist[502],c[502];
 7 int dfs(int k)
 8 {
 9     for(int i=1;i<=n;i++)
10         if(map[k][i] && !vist[i])
11         {
12             vist[i]=1;
13             if(c[i]==0 || dfs(c[i]))
14             {
15                 c[i]=k;
16                 return 1;
17             }
18         }
19         return 0;
20 }
21 int main()
22 {
23     while(~scanf("%d%d",&n,&m))
24     {
25         memset(map,0,sizeof(map));
26         memset(c,0,sizeof(c));
27         int i,x,y,sum=0;
28         for(i=1;i<=m;i++)
29         {
30             scanf("%d%d",&x,&y);
31             map[x][y]=1;
32         }
33         for(i=1;i<=n;i++)
34         {
35            memset(vist,0,sizeof(vist));
36            if(dfs(i))
37               sum++;
38         }
39         printf("%d
",sum);
40     }
41 }