题目链接：http://poj.org/problem?id=3585
给定一棵树，边上面代表的是流量，可以选定一个点作为源点，一个点作为汇点，汇点的出量无限，源点的入量无限，问选择哪一个点能使得树中这个点为源点的流量最大。
采用的算法是二次扫描与换根法，第一次扫描的时候选择一个root自底向上算出d的值，也就是从这个点出发向下的最大流量，一次扫描后root结点的流量是确定的，复制到f[root]中，接下来对自顶向下更新子树的f数组的值。更新的时候用上已经是真实f的父节点的f数组值以及当前点的d数组的值。注意在父节点和子节点是叶子节点的时候要单独计算f函数的值，因为实际上叶子结点计算的d数组值是0，但是实际上应该是inf，所以在d数组是非真实的时候要单独计算。
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 200010; const int inf=0x3f3f3f3f; int n; int head[maxn],nxt[maxn<<1],len[maxn<<1],ver[maxn<<1]; int f[maxn],d[maxn]; int deg[maxn]; int cnt=0; void addedge(int a,int b,int c){ ver[++cnt]=b; len[cnt]=c; nxt[cnt]=head[a]; head[a]=cnt; } void dfs_d(int u,int fa){ d[u]=0; for(int i=head[u];i;i=nxt[i]){ int v=ver[i]; int w=len[i]; if(v==fa)continue; dfs_d(v,u); if(deg[v]==1)d[u]+=w; else d[u]+=min(d[v],w); } } void dfs_f(int u,int fa){ //u及以上的部分f数组已经计算完毕， //通过父节点更新子节点的信息 for(int i=head[u];i;i=nxt[i]){ int v=ver[i]; int w=len[i]; if(v==fa)continue; if(deg[u]==1)f[v]=d[v]+w;//父节点是叶子结点 else if(deg[v]==1)f[v]=min(f[u]-w,w); else f[v]=d[v]+min(f[u]-min(d[v],w),w); dfs_f(v,u);//计算以v为根节点的子树的所有f } } int main(){ int T; scanf("%d",&T); while(T--){ cnt=0; scanf("%d",&n); memset(head,0,sizeof(head)); memset(deg,0,sizeof deg); for(int i=0;i<n-1;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); addedge(a,b,c); addedge(b,a,c); deg[a]++,deg[b]++; } memset(d,0,sizeof(d)); dfs_d(1,-1);//算出d数组 f[1]=d[1]; dfs_f(1,-1); int res=0; for(int i=1;i<=n;i++)res=max(res,f[i]); printf("%d\n",res); } return 0; }
《算法竞赛进阶指南》0x54树形DP POJ3585积蓄程度
原文：https://www.cnblogs.com/randy-lo/p/13412073.html