题意很简单,在一颗树上找最小点覆盖。
将树染成黑白两色,构成一张二分图,然后最大匹配==最小点覆盖即可,所以一次匈牙利就可以求出来了
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <stdlib.h>
using namespace std;
#define N 1505 int n;
struct node
{
int to,next;
}edge[N*]; vector<int>g[N]; int pre[N],cnt;
int cao[N],a[N],b[N];
int cnta,cntb;
int mark[N],frt[N]; void add_edge(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=pre[u];
pre[u]=cnt++;
} void Dfs(int s,int fr,int flag)
{
if(flag==)
{
cao[s]=cnta;
a[cnta]=s;
cnta++;
}else
{
cao[s]=cntb;
b[cntb]=s;
cntb++;
}
for(int p=pre[s];p!=-;p=edge[p].next)
{
int v=edge[p].to;
if(v==fr) continue;
Dfs(v,s,flag^);
}
} int dfs(int s)
{
for(int i=;i<g[s].size();i++)
{
int v=g[s][i];
if(mark[v]==) continue;
mark[v]=;
if(frt[v]==-||dfs(frt[v]))
{
frt[v]=s;
return ;
}
}
return ;
} int main()
{
while(scanf("%d",&n)!=EOF)
{
cnt=;
memset(pre,-,sizeof(pre));
for(int i=;i<n;i++)
{
int x;
scanf("%d",&x);
int num;
scanf(":(%d)",&num);
for(int j=;j<num;j++)
{
int y;
scanf("%d",&y);
add_edge(x,y);
add_edge(y,x);
}
}
//然后就是染色了
cnta=; cntb=;
Dfs(,-,);
//然后再建一张图
for(int i=;i<cnta;i++)
{
g[i].clear();
for(int p=pre[a[i]];p!=-;p=edge[p].next)
{
int v=edge[p].to;
g[i].push_back(cao[v]);
}
}
int ans=;
memset(frt,-,sizeof(frt));
for(int i=;i<cnta;i++)
{
memset(mark,,sizeof(mark));
ans+=dfs(i);
}
printf("%d\n",ans);
}
return ;
}