POJ 3585. Accumulation Degree

发表于 分类于

链接

http://poj.org/problem?id=3585

题意

无根树，已知每条边的容量，求从某个点出发流到所有点的最大流量和

思路

换根法

先任选一点为根，记为 $root$，执行一次树形 DP，求出以该点出发的最大流量：

$dp[i]=\sum \limits_{j \in son(i)}
\begin{cases}
min(w[i][j],dp[j]) & deg[j]>1\
w[i][j] & deg[j]=1
\end{cases}$

接下来记 $f[x]$ 是以 $x$ 为根的最大流量和，显然 $f[root]=dp[root]$，从 $root$ 开始再执行一次树形 DP，假设已求 $f[x]$，考虑其子节点 $y$：

$f[y]=
\begin{cases}
dp[y]+w[x][y] & deg[x]=1\
min(w[x][y],f[x]-w[x][y]) & deg[y]=1\
dp[y]+min(w[x][y],min(f[x]-min(w[x][y],dp[y])) & else
\end{cases}$

这是一次自上向下的推导

代码

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
#include<iostream>
#include<cstring>
using namespace std;
const int N=2e5+5;
const int M=4e5+5;
int n;
int cnt,to[M],val[M],nxt[M],head[N],deg[N];
int dp[N],f[N];
bool st[N];
void init() {
    cnt=0;
    memset(head,0,sizeof head);
    memset(deg,0,sizeof deg);
    memset(st,false,sizeof st);
    memset(dp,0,sizeof dp);
}
void addedge(int u,int v,int w) {
    ++cnt;
    to[cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
    deg[u]++;
}
void dfs1(int u) {
    st[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i],w=val[i];
        if(st[v]) continue;
        dfs1(v);
        if(deg[v]==1) dp[u]+=w;
        else dp[u]+=min(dp[v],w);
    }
}
void dfs2(int u) {
    st[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i],w=val[i];
        if(st[v]) continue;
        if(deg[u]==1) f[v]=dp[v]+w;
        else if(deg[v]==1) f[v]=min(w,f[u]-w);
        else f[v]=dp[v]+min(w,f[u]-min(w,dp[v]));
        dfs2(v);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--) {
        init();
        cin>>n;
        for(int i=1;i<n;i++) {
            int u,v,w;
            cin>>u>>v>>w;
            addedge(u,v,w);
            addedge(v,u,w);
        }
        dfs1(1);
        memset(st,false,sizeof st);
        f[1]=dp[1];
        dfs2(1);
        int res=0;
        for(int i=1;i<=n;i++) res=max(res,f[i]);
        cout<<res<<endl;
    }
     return 0;
}