POJ 1466 Girls and Boys(二分图最大独立集)

POJ 1466 Girls and Boys(二分图最大独立集)

http://poj.org/problem?id=1466

题意:

在一群男女同学之间存在”浪漫关系”,且该关系只存在于男同学与女同学之间.现在给出你比如2号学生与4号学生有浪漫关系(但是没给出你到底2号是男同学还是4号是男同学).给出所有的关系,要你求出一个由学生构成的集合,该集合中任意两人都不存在”浪漫关系”.

分析:

这里我们对于题目的输入数据有这么一个假设,如果1同学与2同学有关系,那么一定有1:num …2 和2:num …1 这样两条输入数据.即关系是相互对应的.

我们把男同学放左边,女同学放右边,如果男i与女j存在关系,那么左i与右j之间就连一条无向边. 其实最终我们要求的就是该二分图的最大独立集.

但是题目并没有给出第i号同学到底是男还是女的信息. 最正确的做法应该是:首先用并查集把所有同学分成多个独立的连通分量.然后每个分量再用一次并查集求出该分量所有同学的性别,之后根据性别来建立二分图求分量最大独立集. 最终把所有分量的最大独立集点数相加 即得到最终结果.

现在用另一种简单的方法做,网上基本都是用的下面这种方法,但是解释得有点不严谨.

假设有下图的”浪漫关系”.

上图需仔细想想,验证一下.

AC代码:

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

struct Max_Match
{
    int n;
    vector<int> g[maxn];
    bool vis[maxn];
    int left[maxn];

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

    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()
    {
        int ans=0;
        for(int i=0;i<n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(match(i)) ans++;
        }
        return ans;
    }
}MM;

int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        MM.init(n);
        for(int i=0;i<n;i++)
        {
            int u,num;
            scanf("%d: (%d)",&u,&num);
            while(num--)
            {
                int v;
                scanf("%d",&v);
                MM.g[u].push_back(v);
            }
        }
        printf("%d\n",n-MM.solve()/2);
    }
    return 0;
}