| Time Limit: 2000MS | Memory Limit: 10000K | |
| Total Submissions: 7487 | Accepted: 3482 |
Description
Input
Output
Sample Input
4 0:(1) 1 1:(2) 2 3 2:(0) 3:(0) 5 3:(3) 1 4 2 1:(1) 0 2:(0) 0:(0) 4:(0)
Sample Output
1 2
没有上司的舞会问题
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN=1505; struct Edge{ int to,next; }es[MAXN*2]; int head[MAXN],tot; int n; void addedge(int u,int v) { es[tot].to=v; es[tot].next=head[u]; head[u]=tot++; } int dp[MAXN][2]; int vis[MAXN]; void dfs(int u) { vis[u]=1; dp[u][0]=0; dp[u][1]=0; int s0=0,s1=0; for(int i=head[u];i!=-1;i=es[i].next) { int v=es[i].to; if(!vis[v]) { dfs(v); s1+=min(dp[v][1],dp[v][0]);//ÈôÑ¡Éϸ¸½Úµã,Ôò×Ó½Úµã¿ÉÑ¡¿É²»Ñ¡ s0+=dp[v][1];//Èôûѡ¸¸½Úµã,Ôò×Ó½Úµã±ØÐëÑ¡ } } dp[u][1]+=(s1+1); dp[u][0]+=s0; } int main() { while(scanf("%d",&n)!=EOF) { tot=0; memset(head,-1,sizeof(head)); memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++) { int u,k; scanf("%d%*c%*c%d%*c",&u,&k); while(k--) { int v; scanf("%d",&v); addedge(u,v); addedge(v,u); } } dfs(0); printf("%d\n",min(dp[0][0],dp[0][1])); } return 0; }
原文：http://www.cnblogs.com/program-ccc/p/5222464.html