HDU 2444 The Accomodation of Students(二分图判定+最大匹配)

HDU 2444 The Accomodation of Students(二分图判定+最大匹配)

http://acm.hdu.edu.cn/showproblem.php?pid=2444

题意:

给你N个学生与M对关系,每个关系形如(i,j),表示第i个学生与第j个学生相互认识. 现在要你将N个学生分成两组,每组中的任意两个学生都不相互认识.

如果N个学生能分组的话,那么就将这N个学生放到尽量多的双人房中去.每个房间放2个相互认识的人.问你最多需要多少房间?

分析:

首先第一步将N个学生分成两类就是看能否将图二分.假设每个学生是一个节点,如果i学生与j学生认识,那么i点和j点之间连一条无向边. 然后我们将图分成两部分,左边部分和右边部分.且各部分内部不存在边,所有边一定是左边与右边点之间的边.(这就是二分图的定义)

判断二分图的话直接用刘汝佳的模板即可.

如果该图能二分, 直观的做法是将所有点重新编号分成左右两边.然后再计算最大匹配. 但是给点重新编号明显比较麻烦,这里我们将原图翻倍处理,然后直接计算出翻倍后图的最大匹配数X. 最终X/2就是我们所求.

翻倍原图具体原理证明在POJ1466:

http://blog.csdn.net/u013480600/article/details/38638219

AC代码:

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 200+10;

struct Max_Match
{
    int n;
    int color[maxn];//颜色数组,用于二分图判定
    vector<int> g[maxn];
    bool vis[maxn];
    int left[maxn];

    void init(int n)
    {
        this->n=n;
        for(int i=1;i<=n;i++) g[i].clear();
        memset(left,-1,sizeof(left));
    }

    bool bipartite(int u)
    {
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i];
            if(color[v] == color[u]) return false;
            else if(color[v]==0)
            {
                color[v]= 3-color[u];
                if(!bipartite(v)) return false;
            }
        }
        return true;
    }

    bool match(int u)
    {
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i];
            if(!vis[v])
            {
                vis[v]=true;
                if(left[v]==-1 || match(left[v]))
                {
                    left[v]=u;
                    return true;
                }
            }
        }
        return false;
    }

    int solve()
    {
        memset(color,0,sizeof(color));
        for(int i=1;i<=n;i++)if(!color[i])//因为该图不一定连通,所以需要所有点做起点判断一遍
        {
            color[i]=1;
            if(!bipartite(i)) return -1;
        }

        int ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(match(i)) ans++;
        }
        return ans;
    }
}MM;

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        MM.init(n);
        while(m--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            MM.g[u].push_back(v);//判断2分图,由于是无向的,所以需要添加两次边
            MM.g[v].push_back(u);//计算原图翻倍的最大匹配,也需要添加两次边
        }
        int ans=MM.solve();
        if(ans==-1) printf("No\n");
        else printf("%d\n",ans/2);
    }
    return 0;
}