poj3585 Accumulation Degree 题解报告-蒲公英云

poj3585 Accumulation Degree 题解报告

港控/mmm° 2021-12-19 04:55 276阅读 0赞

题目传送门

【题目大意】

一个树形水系，有$n$个结点，根结点称为源点，叶子结点称为汇点，每条边都有水量限制$C_{x,y}$($x,y$为这条边的两个端点)，源点单位时间流出的水量称为整个水系的流量，求以哪一个结点作为源点整个水系的流量最大。

【思路分析】

这是一道“不定根”的树形DP问题，这类题目的特点是，给定一个树形结构，需要以每个结点为根进行一系列统计。我们一般通过两次扫描来求解此类问题：

1.第一次扫描，任选一个点为根，在“有根树”上执行一次树形DP。

2.第二次扫描，从刚才选出的根出发，对整棵树执行一次DFS，在每次递归前进行自上而下的推导，计算出“换根”之后的解。

首先，我们任选一个结点$root$，然后树形DP一下，求出$D_{root}$数组($D[i]$表示在以$i$为根的子树中流量的最大值)。然后设$f[x]$表示以x为源点，流向整个水系的最大流量，则显然$D[root]=f[root]$。假设$f[x]$已经求出，考虑其子结点$y$，则$f[y]$包含两部分：

1.从$y$流向以$y$为根的子树的流量，已经计算出来。

2.从$y$沿着到父节点$x$的河道，进而流向水系中其他部分的流量。

由题意可得，从$x$流向$y$的流量为$min(D[y],c[x][y])$，所以从$x$流向除$y$以外其他部分的流量就是二者之差$f[x]-min(D[y],c[x][y])$。于是，把$y$作为源点，先流到$x$，再流向其他部分的流量就是把这个“差”再与$c[x][y]$取较小值后的结果。

if(du[x]>1)\to f[y]=D[y]+min(f[x]-min(D[y],c[x][y])-c[x][y])

if(du[x]==1)\to f[y]=D[y]+c[x][y]

这是一个由上而下的递推方程，我们通过一次DFS即可实现。

【代码实现】

1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<cstring>
 5 #define rg register
 6 #define go(i,a,b) for(rg int i=a;i<=b;i++)
 7 #define mem(a,b) memset(a,b,sizeof(a))
 8 using namespace std;
 9 const int N=2e5+2;
10 int T,n,du[N];
11 struct node{
     int to,w;};
12 vector<node> c[N];
13 bool v[N];
14 int d[N],f[N];
15 void clean(){
16     mem(v,0);mem(du,0);mem(d,0);mem(f,0);
17     go(i,1,n) c[i].clear();
18 }
19 void dp(int x){
20     v[x]=1;
21     int size=c[x].size()-1;
22     go(i,0,size){
23         int to=c[x][i].to,w=c[x][i].w;
24         if(v[to]) continue;
25         dp(to);
26         if(du[to]==1) d[x]+=w;
27         else d[x]+=min(d[to],w);
28     }
29     return;
30 }
31 void dfs(int x){
32     v[x]=1;
33     int size=c[x].size()-1;
34     go(i,0,size){
35         int to=c[x][i].to,w=c[x][i].w;
36         if(v[to]) continue;
37         if(du[x]==1) f[to]=d[to]+w;
38         else f[to]=d[to]+min(f[x]-min(d[to],w),w);
39         dfs(to);
40     }
41     return;
42 }
43 int main(){
44     scanf("%d",&T);
45     while(T--){
46         scanf("%d",&n);clean();
47         int x,y,z;
48         go(i,1,n-1){
49             scanf("%d%d%d",&x,&y,&z);
50             c[x].push_back((node){y,z});c[y].push_back((node){x,z});
51             du[x]++;du[y]++;
52         }
53         dp(1);
54         f[1]=d[1];mem(v,0);
55         dfs(1);
56         int ans=0;
57         go(i,1,n) ans=max(ans,f[i]);
58         printf("%d\n",ans);
59     }
60     return 0;
61 }