hdu 1054 最小点覆盖

这题就是运用到了二分图的三个重要结论之一：

最小点覆盖数： 最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。可以证明：最少的点（即覆盖数）＝最大匹配数

如果图Ｇ满足二分图条件，则可以用二分图匹配来做．最大独立集点数 = N - 最大匹配数。

#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;

int head[1505],vis[1505],match[1505];
struct NDOE
{
    int to,next;
}edge[100000];
int n,c,ans;

int dfs(int x)
{
    int i,to;
    for(i=head[x];i!=-1;i=edge[i].next)
    {
        to=edge[i].to;
        if(!vis[to])
        {
            vis[to]=1;
            if(match[to] == -1 || dfs(match[to]))
            {
                match[to]=x;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    while(~scanf("%d",&n))
    {
        int i,j,k;
        int num,a,b;
        for(i=0;i<n;i++) head[i]=-1,match[i]=-1;
        for(i=0,c=0;i<n;i++)
        {
            scanf("%d:(%d)",&a,&num);
            while(num--)
            {
                scanf("%d",&b);
                edge[c].to=b,edge[c].next=head[a],head[a]=c++;
                edge[c].to=a,edge[c].next=head[b],head[b]=c++;
            }
        }
        for(i=0,ans=0;i<n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i)) ans++;
        }
        printf("%d\n",ans/2);
    }
}

hdu 1054 最小点覆盖,布布扣,bubuko.com

hdu 1054 最小点覆盖

原文：http://blog.csdn.net/alone_l/article/details/20216539