HDU1054 Strategic Game

题面:http://acm.hdu.edu.cn/showproblem.php?pid=1054

本题是求树的最小点覆盖裸题。Code: #include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<ctime> using namespace std; const int N=6005; int n,f[N][2],Head[N],Cnt; bool vis[N]; struct Node{int v,Next; }Edge[N*2]; void Push(int u,int v){++Cnt;Edge[Cnt].v=v;Edge[Cnt].Next=Head[u];Head[u]=Cnt; } void dfs(int u,int fa){f[u][0]=0;f[u][1]=1;for(int i=Head[u];i;i=Edge[i].Next){int v=Edge[i].v;if(v==fa){continue;}dfs(v,u);f[u][0]+=f[v][1];f[u][1]+=min(f[v][0],f[v][1]);} } int main(){while(~scanf("%d",&n)){memset(Head,0,sizeof(Head));Cnt=0;for(int i=1;i<=n;i++){int u,k;scanf("%d:(%d)",&u,&k);u++;for(int j=1;j<=k;j++){int v;scanf("%d",&v);v++;Push(u,v);Push(v,u);}}memset(f,0,sizeof(f));dfs(1,0);printf("%d\n",min(f[1][0],f[1][1]));}return 0; }

转载于:https://www.cnblogs.com/ukcxrtjr/p/11243533.html

总结

以上是生活随笔为你收集整理的HDU1054 Strategic Game的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。