切题ing！！！！！
经典树形DP，以前写的太搓了，终于学会简单写法了....
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <map> #include <queue> #include <set> #include <vector> #define MOD 100000000 #define LL __int64 using namespace std; int dp[7000][2]; struct node { int u,v,next; }edge[7000]; int first[7000]; int flag[7000]; int p[7000]; int t; void CL() { t = 0; memset(first,-1,sizeof(first)); } void add(int u,int v) { edge[t].u = u; edge[t].v = v; edge[t].next = first[u]; first[u] = t ++; } int dfs(int x,int st,int fa) { int sum = 0,i,v; if(dp[x][st] != -1) return dp[x][st]; for(i = first[x];i != -1;i = edge[i].next) { v = edge[i].v; if(v == fa) continue; dfs(v,0,x); dfs(v,1,x); if(st == 0) sum += max(dp[v][0],dp[v][1]); else sum += dp[v][0]; } if(st == 1) return dp[x][1] = sum + p[x]; else return dp[x][0] = sum; } int main() { int n,i,u,v; while(scanf("%d",&n)!=EOF) { CL(); memset(dp,-1,sizeof(dp)); for(i = 1;i <= n;i ++) { scanf("%d",&p[i]); } memset(flag,0,sizeof(flag)); for(;;) { scanf("%d%d",&u,&v); if(!u&&!v) break; add(v,u); flag[u] = 1; } for(i = 1;i <= n;i ++) { if(!flag[i]) add(0,i); } printf("%d\n",dfs(0,0,-1)); } return 0; }
经典两次DFS，树形DP，也可以用最长路来做，我以前会的，忘了好多...
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <map> #include <queue> #include <set> #include <vector> #define MOD 100000000 #define LL __int64 using namespace std; int dp[10001][2]; int ans[10001]; int flag[10001]; struct node { int u,v,w,next; }edge[20001]; int t; int first[10001]; void CL() { t = 1; memset(first,-1,sizeof(first)); } void add(int u,int v,int w) { edge[t].u = u; edge[t].v = v; edge[t].w = w; edge[t].next = first[u]; first[u] = t ++; } void dfs1(int x) { int i,v,max1 = 0,max2 = 0; flag[x] = 1; for(i = first[x];i != -1;i = edge[i].next) { v = edge[i].v; if(flag[v]) continue; dfs1(v); if(max1 < dp[v][0] + edge[i].w) { max2 = max1; max1 = dp[v][0] + edge[i].w; } else if(max1 == dp[v][0] + edge[i].w) max2 = dp[v][0] + edge[i].w; else if(max2 < dp[v][0] + edge[i].w) max2 = dp[v][0] + edge[i].w; } dp[x][0] = max1; dp[x][1] = max2; } void dfs2(int x,int fa) { int i,v; flag[x] = 1; ans[x] = max(dp[x][0],fa); for(i = first[x];i != -1;i = edge[i].next) { v = edge[i].v; if(flag[v]) continue; if(dp[x][0] == dp[v][0] + edge[i].w) dfs2(v,max(fa,dp[x][1])+edge[i].w); else dfs2(v,max(fa,dp[x][0])+edge[i].w); } } int main() { int i,n,v,w; while(scanf("%d",&n)!=EOF) { CL(); for(i = 2;i <= n;i ++) { scanf("%d%d",&v,&w); add(v,i,w); add(i,v,w); } memset(flag,0,sizeof(flag)); dfs1(1); //for(i = 1;i <= n;i ++) //printf("%d %d\n",dp[i][0],dp[i][1]); memset(flag,0,sizeof(flag)); dfs2(1,0); for(i = 1;i <= n;i ++) printf("%d\n",ans[i]); } return 0; }
以前做的时候，看错题了...这题是把所有的路，放一个士兵看守，那么如果根不放士兵，那么所有的子节点都要放。
#include <cstdio> #include <cstring> #include <string> #include <iostream> using namespace std; #define INF 100000000 struct node { int u,v,next; }edge[1501]; int dp[1501][2]; int flag[1501]; int t; int first[1501]; void CL() { t = 0; memset(flag,0,sizeof(flag)); memset(dp,0,sizeof(dp)); memset(first,-1,sizeof(first)); } void add(int u,int v) { edge[t].u = u; edge[t].v = v; edge[t].next = first[u]; first[u] = t ++; } void dfs(int x) { int i,v; for(i = first[x];i != -1;i = edge[i].next) { v = edge[i].v; dfs(v); } for(i = first[x];i != -1;i = edge[i].next) { v = edge[i].v; dp[x][1] += min(dp[v][0],dp[v][1]); dp[x][0] += dp[v][1]; } dp[x][1] ++; } int main() { int i,j,n,m,u,v; while(scanf("%d",&n)!=EOF) { CL(); for(i = 1;i <= n;i ++) { scanf("%d:(%d)",&u,&m); for(j = 1;j <= m;j ++) { scanf("%d",&v); flag[v] = 1; add(u,v); } } for(i = 0;i < n;i ++) { if(!flag[i]) { dfs(i); printf("%d\n",min(dp[i][0],dp[i][1])); break; } } } return 0; }
原文：http://www.cnblogs.com/naix-x/p/3898026.html
