poj3585 Accumulation Degree 题解报告

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

[题目传送门][Link 1]

**【题目大意】**

一个树形水系，有$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即可实现。

**【代码实现】**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

代码戳这里

转载于:https://www.cnblogs.com/THWZF/p/11010281.html

[Link 1]: http://poj.org/problem?id=3585
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211218/c911bade38544f2997c599b2cf7aae32.png