hdu 1054 Strategic Game 点覆盖数

1054 Strategic Game

      典型的点覆盖。

     因为是树状图所以可以看成二分，但因为不好确定每一层，所以扩展成n-n的二分

      点覆盖数==最大匹配数（双向）/2

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <cstdio>
#include <cstring>
#include <vector>
#define maxn 1505
using namespace std;
int n,t,m,pre[maxn];
bool vis[maxn];
vector<int> edge[maxn];
bool dfs(int now)
{
    int len=edge[now].size();
    for(int i=0;i<len;i++)
    {
        int k=edge[now][i];
        if(vis[k])continue;
        vis[k]=1;
        if(pre[k]!=-1&&!dfs(pre[k]))continue;
        pre[k]=now;
        return 1;
    }
    return 0;
}
int main()
{
    while(~scanf("%d",&n))
    {
        int i,j,k,ans=0;
        for(i=0;i<n;i++)edge[i].clear();
        for(i=0;i<n;i++)
        {
            scanf("%d:(%d)",&k,&m);
            for(j=0;j<m;j++)
            {
                scanf("%d",&t);
                edge[k].push_back(t);//建双向图
                edge[t].push_back(k);
            }
        }
        memset(pre,-1,sizeof(pre));
        for(i=0;i<n;i++)
        {
            memset(vis,0,sizeof(vis));
            ans+=dfs(i);
        }
        if(n==1)ans=2;
        printf("%d\n",ans/2);
    }
    return 0;
}