POJ3585 Accumulation Degree （树形DP-二次扫描与换根）

本题属于不定根的树形DP，若以每个节点为根求解一次，复杂度太高，所以可以用换根的技巧。

d[u]表示以u为根向下可以流的最大流量，这个是比较好求的，直接遍历到叶子节点，由子节点信息更新父节点。然后进行第二次遍历，从上往下，子节点的信息由父节点更新。

这就是换根法的基本思路。

本题转移方程还是比较好想的，画图分析一下就行了。

 1 #include<cstdio>

 2 #include<cstring>

 3 #include<algorithm>

 4 using namespace std;

 5 const int MAXN=200200;

 6 const int MAXE=400400;

 7 const int INF=0x3f3f3f3f;

 8 struct E{

 9     int v,w,next;

10 }edge[MAXE];

11 int head[MAXN],cnt,dp[MAXN],d[MAXN],val[MAXN],deg[MAXN];

12 int n,T;

13

14 void add(int u,int v,int w){

15     edge[cnt].v=v;

16     edge[cnt].w=w;

17     edge[cnt].next=head[u];

18     head[u]=cnt++;

19 }

20

21 void dfs1(int u,int fa){

22     d[u]=0;

23     for(int i=head[u];~i;i=edge[i].next){

24         int v=edge[i].v;

25         if(v==fa) continue;

26         dfs1(v,u);

27         if(deg[v]==1) d[u]+=edge[i].w;

28         else d[u]+=min(d[v],edge[i].w);

29     }

30 }

31

32 void dfs2(int u,int fa){

33     for(int i=head[u];~i;i=edge[i].next){

34         int v=edge[i].v;

35         if(v==fa) continue;

36         if(deg[u]==1) dp[v]=d[v]+edge[i].w;

37         else dp[v]=d[v]+min(dp[u]-min(d[v],edge[i].w),edge[i].w);

38         dfs2(v,u);

39     }

40 }

41

42 void init(){

43     memset(head,-1,sizeof(head));

44     memset(d,0,sizeof(d));

45     memset(dp,0,sizeof(dp));

46     memset(deg,0,sizeof(deg));

47     cnt=0;

48 }

49

50 int main(){

51     scanf("%d",&T);

52     while(T--){

53         scanf("%d",&n);

54         init();

55         for(int i=1;i<n;i++){

56             int u,v,w;

57             scanf("%d%d%d",&u,&v,&w);

58             add(u,v,w);

59             add(v,u,w);

60             deg[u]++;

61             deg[v]++;

62         }

63         dfs1(1,0);

64         dp[1]=d[1];

65         dfs2(1,0);

66         int ans=0;

67         for(int i=1;i<=n;i++)

68             ans=max(ans,dp[i]);

69         printf("%d\n",ans);

70     }

71     return 0;

72 }

巴特西

POJ3585 Accumulation Degree （树形DP-二次扫描与换根）

最新文章

热门文章