POJ3585AccumulationDegree--二次扫描与换根

题目链接

https://cn.vjudge.net/problem/POJ-3585

找到一个点,如果其成为河水发源地,使整棵树的流量最大,有些河道会限制流量

真- 网络流

分析

学到了一个船新骚操作—二次扫描与换根!

首先我们来$naive$的做法,枚举每个点作为发源地,然后进行一次树形DP

$f[now]$表示在$now$为根的子树中的最大流量,那么根据题目定义

$f[now] = \sum min(f[son],infc(now,son))$

特殊地,如果$son$的度数为$1$(相当于叶节点)那么$f[now]+= infc(now,son)$

然而这样的时间复杂度是$O(N^2)$

然后二次扫描与换根法让我们只用两次遍历就能得出所有节点为根时的解

核心思想是理解子节点到父节点中哪些信息被更改与转移,不同于之前的DP,这回我们的信息自顶向下转移

显然$son$对$f[now]$,做出的贡献是$min(f[son],infc(now,son))$

所以以$now$为根的树中除去$son$的子树剩下的流量就是$ans[now]-min(f[son],infc(now,son))$,

又因为假如以$son$为根那么答案显然是原来$DFS$中求得$son$子树的解$f[son]$加上父亲节点水流到它的贡献

于是$ans[son]=f[son]+min(infc(now,son),ans[now]-min(infc(now,son),f[son])) $

特殊地,如果$now$是度数为1(相当叶节点),那么$ans[son]=f[son]+infc(now,son)$

代码

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
74
75
76
77
78
79
80
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <iostream>
#define ll long long 
#define ri register int 
using std::min;
using std::max;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
const int maxn=200005;
const int inf=0x7fffffff;
struct Edge{
    int ne,to,dis;
}edge[maxn<<1];
int h[maxn],num_edge=0;
inline void add_edge(int f,int to,int c){
    edge[++num_edge].ne=h[f];
    edge[num_edge].to=to;
    edge[num_edge].dis=c;
    h[f]=num_edge;
}
int deg[maxn];
int f[maxn],n,d[maxn],ans=-inf;
int infc[maxn];//流量
void dfs_1(int now,int fa){
    int v;bool flag=0;
    d[now]=0;
    for(ri i=h[now];i;i=edge[i].ne){
        v=edge[i].to;
        if(v==fa)continue;
        flag=1;
        infc[v]=edge[i].dis;
        dfs_1(v,now);
        if(deg[v]==1)d[now]+=infc[v];
		else d[now]+=min(d[v],infc[v]);
	}
    return ;
}
void dfs_2(int now,int fa){
    int v;
    for(ri i=h[now];i;i=edge[i].ne){
        v=edge[i].to;
        if(v==fa)continue;
        if(deg[now]==1)f[v]=d[v]+infc[v];
        else f[v]=d[v]+min(infc[v],f[now]-min(infc[v],d[v]));
        dfs_2(v,now);
    }
    ans=max(ans,f[now]);
    return ;
}
int main(){
	int T;
	int x,y,z;
    read(T);
    while(T--){
        read(n);
        num_edge=0,ans=-inf;
        memset(h,0,sizeof(h));
        memset(deg,0,sizeof(deg));
        for(ri i=1;i<n;i++){
            read(x),read(y),read(z);
            deg[x]++,deg[y]++;
            add_edge(x,y,z);
            add_edge(y,x,z);
        }
        dfs_1(1,0);
        f[1]=d[1];
        dfs_2(1,0);
        printf("%d\n",ans);
    }
    return 0;
}