树形dp之最小点覆盖（模板）

最小点覆盖：一条边至少要选一个点
这题测评姬的编译器只能选c++,不能选c++11和c++14,很古老，不能用万能头，不能用string
注意这题有0号结点，所以（前向星和平常不一样的地方（以后就用下面这种，防止0号结点））：
              1、for(int i=head[x];i!=-1;i=edge[i].next)
              2、memset(edge,-1,sizeof(edge));
              //3、memset(head,-1,sizeof(head));  //这个不需要

转移方程：f[x][0]= f[i][1];
f[x][1]= min(f[i][1],f[i][0])+1;

//#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
using namespace std;
int const N=2e3+7;
int n,cnt;
int head[N];
struct node{
int a,next,len;
}edge[N<<1];
void add(int x,int y,int len){
edge[++cnt].a =y;
edge[cnt].len =len;
edge[cnt].next =head[x];
head[x]=cnt;
}
int vis[N],f[N][2],ans=0x3f3f3f3f;</cstring></iostream>

void dfs(int x){
    f[x][1]=1;f[x][0]=0;
    vis[x]=1;   //防止它儿子访问父亲，这里我真的忘了好多次
    for(int i=head[x];i!=-1;i=edge[i].next){
        if(vis[edge[i].a]) continue;
        vis[edge[i].a]=1;
        dfs(edge[i].a);
        f[x][0]+=f[edge[i].a][1];
        f[x][1]+=min(f[edge[i].a][0],f[edge[i].a][1]);
    }
    ans=min(f[x][0],f[x][1]);
}

int main(){
while(cin >> n){

//初始化很重要
        cnt=0;ans=0x3f3f3f3f;
        memset(vis,0,sizeof(vis));
        //memset(edge,-1,sizeof(edge));  //这个不需要
        memset(head,-1,sizeof(head));  //这句也要记住
        memset(f,0x3f,sizeof(f));

//
while(n--){
//string str;
//cin >> str;
//int a=str[0]-'0',z=str[3]-'0';
int a,z;
scanf("%d:(%d)",&a,&z);
for(int j=1;j<=z;++j){
int b;cin >> b;
add(a,b,1);add(b,a,1);
}
}
dfs(1);
cout << ans << endl;
}
return 0;
}