题意

给定一颗无向带权树，权值代表两点间流量的最大值，现在要你找出一个节点作为源点，向叶子节点流水（根节点的水流可以认为无限大），使整棵树的流水量最大。

分析

本题是一个“不定根”的树形dp问题，很容易想到一种朴素的解法：枚举源点，每次做一次树形dp，时间复杂度 O(N²)。

我们如果用“换根法”代替源点的枚举，就可以在O(N)的时间内解决问题。

设c(x,y)表示接x,y树边的权值,deg[x] 表示x节点的度数

设D[x]表示在以x为的子树中，把x作为源点，从x出发流向子树的流量最大是多少。

D[x]=∑c(x,y) _ded[y]=1 + ∑min(D[y],c(x,y)) _deg[y]>1（y∈son[x]）

void dp(int x){
    vis[x]=1;
    d[x]=0;
    for(int i=Head[x];i;i=Next[i]){
        int y=to[i];
        if(vis[y]) continue;
        dp(y);
        if(deg[y]==1) d[x]+=edge[i]; //edge[i]即为c(x,y) 
        else d[x]+=min(d[y],edge[i]); 
    }
}

 

首先，先任选一个点作为源点，记为root,然后采用上述代码进行一次树形dp,求出D数组。

设F[x]表示把x当做源点，流向整个水系的最大流量是多少。显然，F[root]=D[root]。

假设F[x]已被正确求出，考虑其子节点y，F[y]包括两部分。

1. 从y流向以y为根的子树的流量，即为D[y]。
2. 从y沿着到x节点的河道，进而流向水系中其他部分的流量。

 

               以1为源点                              以2为源点

因为F[x]为把x作为源点的总流量，从x流向y的流量为min(D[y],c(x,y)),所以x流向其他子节点的流量就是二者之差。当然，deg[x]=1是要特判。

当deg[x]>1时，F[y]=D[y]+min(F[x]-min(D[y],c(x,y)),c(x,y))

当deg[x]=1时，F[y]=D[y]+c(x,y)

这是一个自上而下的转移方程式，只要从root为根节点，dfs一遍即可。

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int Head[N],edge[N<<1],to[N<<1],Next[N<<1];
int tot,n,T;
void add(int u,int v,int w){
    to[++tot]=v;
    edge[tot]=w;
    Next[tot]=Head[u];
    Head[u]=tot;
}
int d[N],f[N],vis[N],deg[N];
void init(){
    memset(Head,0,sizeof(Head));
    tot=0;
    memset(d,0,sizeof(d));
    memset(vis,0,sizeof(vis));
    memset(f,0,sizeof(f));
    memset(deg,0,sizeof(deg));
}
void dp(int x){ //求D数组 
    vis[x]=1;
    d[x]=0;
    for(int i=Head[x];i;i=Next[i]){
        int y=to[i];
        if(vis[y]) continue;
        dp(y);
        if(deg[y]==1) d[x]+=edge[i];
        else d[x]+=min(d[y],edge[i]); 
    }
}
void dfs(int x){ //求F数组 
    vis[x]=1;
    for(int i=Head[x];i;i=Next[i]){
        int y=to[i];
        if(vis[y]) continue;
        if(deg[x]==1) f[y]=d[y]+edge[i];
        else f[y]=d[y]+min(f[x]-min(d[y],edge[i]),edge[i]); 
        dfs(y);
    }
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        init();  //初始化不能忘 
        for(int i=1;i<n;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
            deg[u]++,deg[v]++;  //求度数 
        }
        int root=1;
        dp(root);
        memset(vis,0,sizeof(vis));
        f[root]=d[root];
        dfs(root);
        int ans=0;
        for(int i=1;i<=n;i++)
            ans=max(ans,f[i]); 
        printf("%d\n",ans);
    }
    return 0;
}