题意：就是求最小顶点覆盖。树形dp过了的题，看着是说怎么这么眼熟
思路：这个二分图比较好想的，找个根，与根的最短距离为奇数的点丢在一部分，是偶数的点丢在另外一部分，然后连边求边的匹配。
讲真我现在看到一些图还是觉得懵，不知道如何建图...今天看网络流好不容易把那个最基础的算法弄懂了点点，想要看一下题，结果第一题就不知道怎么建图....有点绝望....
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
const int maxn = 2000,maxe = 6e3;
struct node
{
int to,next;
node(){}
node(int a,int b){to = a; next = b;}
}edge[maxe];
int edgenum;
int h[maxn],d[maxn],in[maxn],out[maxn],used[maxn],belong[maxn];
void init()
{
for(int i = 0; i < maxn; i++)
h[i] = -1, in[i] = out[i] = belong[i] = 0;
edgenum = 0;
}
void add(int f,int t)
{
edge[edgenum] = node(t,h[f]);
h[f] = edgenum++;
}
void pred(int u,int deep,int pre)
{
d[u] = deep;
for(int i = h[u]; ~i; i = edge[i].next)
{
//cout << "this" << endl;
int v = edge[i].to;
if(v != pre)
pred(v,deep+1,u);
}
}
bool Find(int u)
{
for(int i = h[u] ; ~i; i = edge[i].next)
{
int v = edge[i].to;
if(used[v]) continue;
used[v] = 1;
if(!belong[v] || Find(belong[v]))
{
belong[v] = u;
return true;
}
}
return false;
}
void solve()
{
int ans = 0;
for(int i = 1; i <= n; i++)
{
if(d[i]%2==0)
{
memset(used,0,sizeof(used));
if(Find(i)) ans++;
}
}
printf("%d\n",ans);
}
int main()
{
int a,b,c;
while(~scanf("%d",&n))
{
init();
for(int i = 0; i < n; i++)
{
scanf("%d:(%d)",&a,&b);
a++;
for(int j = 0; j < b ; j++)
{
scanf("%d",&c); c++;
add(a,c); add(c,a);
out[a]++; in[c]++;
}
}
int root = -1;
for(int i = 1; i <= n; i++)
if(!in[i]) {root = i;break;}
pred(root,0,-1);
solve();
}
return 0;
}