0x50 动态规划（0x54 树形DP）例题3：积蓄程度（题解）_积蓄程序题解

题意

神仙题

【题目描述】
 有一个树形的水系，由 N-1 条河道和 N 个交叉点组成。
 我们可以把交叉点看作树中的节点，编号为 1~N，河道则看作树中的无向边。
 每条河道都有一个容量，连接 x 与 y 的河道的容量记为 c(x,y)。
 河道中单位时间流过的水量不能超过河道的容量。
 有一个节点是整个水系的发源地，可以源源不断地流出水，我们称之为源点。
 除了源点之外，树中所有度数为 1 的节点都是入海口，可以吸收无限多的水，我们称之为汇点。
 也就是说，水系中的水从源点出发，沿着每条河道，最终流向各个汇点。
 在整个水系稳定时，每条河道中的水都以单位时间固定的水量流向固定的方向。
 除源点和汇点之外，其余各点不贮存水，也就是流入该点的河道水量之和等于从该点流出的河道水量之和。
 整个水系的流量就定义为源点单位时间发出的水量。
 在流量不超过河道容量的前提下，求哪个点作为源点时，整个水系的流量最大，输出这个最大值。  
  【输入格式】
 输入第一行包含整数T，表示共有T组测试数据。
 每组测试数据，第一行包含整数N。
 接下来N-1行，每行包含三个整数x,y,z，表示x，y之间存在河道，且河道容量为z。
 节点编号从1开始。  
  【输出格式】
 每组数据输出一个结果，每个结果占一行。
 数据保证结果不超过2^31−1。  
  【数据范围】
N≤2*10^5  
  【输入样例】
1
 5
 1 2 11
 1 4 13
 3 4 5
 4 5 10   
  【输出样例】
26 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

思路

我的妈呀，如果以前没做仓鼠找sugar II估计我还真做不出这道题目。

看到这种找根且还带树形DP的题目，脑子里面要马上树立一个正确的价值观，就是我们先固定一个根。

很明显，我们只要固定了一个根的话，算出他的流量不是手到擒来？

我们设$f[i]$表示这棵子树以$i$为汇点的话，那么流量是多少，随便DP一下就可以算出$f[1]$，同时我们又发现，我们貌似是可以$O(1)$转移的！

把当树根为$1$的情况转移到树根为$2$的情况貌似只用$O(1)$，即减去$2$对$1$的贡献，然后把$1$对$2$的贡献加到$2$，然后我们就可以算出树根为$2$的值了，那么我们再DFS一遍不就可以$O(n)$解决了吗？

当然根节点如果只有一个儿子的话那么转移到儿子后他的$f$为$inf$。

#include<cstdio>
#include<cstring>
#define  N  210000
#define  M  410000
#define  inf  2147483647
using  namespace  std;
struct  node
{
	int  y,c,next;
}a[M];int  len,last[N];
inline  void  ins(int  x,int  y,int  c){len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}
int  f[N]/*表示的是以1为根的话，那么这个点的水流是多少*/,dp[N]/*表示以他为根时的答案。*/;
int  siz[N],dep[N];
int  n;
inline  int  mymin(int  x,int  y){return  x<y?x:y;}
inline  int  mymax(int  x,int  y){return  x>y?x:y;}
void  dfs1(int  x,int  fa)
{
	siz[x]=1;
	for(int  k=last[x];k;k=a[k].next)
	{
		int  y=a[k].y;
		if(y!=fa)
		{
			dep[y]=dep[x]+1;
			dfs1(y,x);
			f[x]+=mymin(f[y],a[k].c);siz[x]+=siz[y];
		}
	}
	if(siz[x]==1)f[x]=inf;
}
void  dfs2(int  x,int  fa)//表示以x为根的答案。 
{
	dp[x]=f[x];//索性继承 
	for(int  k=last[x];k;k=a[k].next)
	{
		int  y=a[k].y;
		if(y!=fa)
		{
			int  now=f[x];
			if(siz[x]-siz[y]==1  &&  dep[x]==0/*在根节点*/)f[x]=inf;
			else  f[x]-=mymin(f[y],a[k].c);
			if(siz[y]==1)f[y]=mymin(f[x],a[k].c);//特判这个点是不是叶子节点 
			else  f[y]+=mymin(f[x],a[k].c);
			dfs2(y,x);
			if(siz[y]==1)f[y]=inf;
			else  f[y]-=mymin(f[x],a[k].c);
			f[x]=now;
		}
	}
}
int  main()
{
	int  T;scanf("%d",&T);
	while(T--)
	{
		len=0;memset(last,0,sizeof(last));
		memset(f,0,sizeof(f));
		memset(dp,0,sizeof(dp));//暴力初始化
		scanf("%d",&n);
		for(int  i=1;i<n;i++)
		{
			int  x,y,z;scanf("%d%d%d",&x,&y,&z);
			ins(x,y,z);ins(y,x,z);
		}
		dfs1(1,0);
		dfs2(1,0);
		int  ans=0;
		for(int  i=1;i<=n;i++)ans=mymax(dp[i],ans);
		printf("%d\n",ans);
	}
	return  0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73