题目描述
有一个树形的水系，由 N-1 条河道和 N 个交叉点组成。我们可以把交叉点看作树中的节点，编号为1~N，河道则看作树中的无向边。每条河道都有一个容量，连接 x 与 y 的河道的容量记为 c(x,y)。河道中单位时间流过的水量不能超过河道的容量。有一个节点是整个水系的发源地，可以源源不断地流出水，我们称之为源点。除了源点之外，树中所有度数为1的节点都是入海口，可以吸收无限多的水，我们称之为汇点。也就是说，水系中的水从源点出发，沿着每条河道，最终流向各个汇点。在整个水系稳定时，每条河道中的水都以单位时间固定的水量流向固定的方向。除源点和汇点之外，其余各点不贮存水，也就是流入该点的河道水量之和等于从该点流出的河道水量之和。整个水系的流量就定义为源点单位时间发出的水量。在流量不超过河道容量的前提下，求哪个点作为源点时，整个水系的流量最大，输出这个最大值。N≤2*〖10〗^5。
输入格式
The first line of the input is an integer T which indicates the number of test cases.
The first line of each test case is a positive integer n.
Each of the following n - 1 lines contains three integers x, y, z separated by spaces, representing there is an edge between node x and node y, and the capacity of the edge is z. Nodes are numbered from 1 to n.
All the elements are nonnegative integers no more than 200000.
You may assume that the test data are all tree metrics.
输出格式
For each test case, output the result on a single line.
显然是二次扫描与换根法的树形dp。
我们先dfs一遍求出当根为1时的答案：设f(i)表示i的流量。那么状态转移方程就是：
[v{in}son(u)\
f[u]= left{ egin{array}{rcl}
edge(u,v) & degree[v]=1\
Min(f[v],edge(u,v)) & degree[v]{
eq}1
end{array}
ight.
]
设dp(i)表示当i为根时i的流量，然后考虑换根的代价：
[dp[v]= left{ egin{array}{rcl}
f[v]+edge(u,v) & degree[u]=1\
f[v]+Min(dp[u]-Min(f[v],edge(u,v)),edge(u,v)) & degree[u]{
eq}1
end{array}
ight.
]
目标状态就是Max(dp(i))。
时间复杂度为O(N)。
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 200001
using namespace std;
struct edge{
int to,dis,next;
edge(){}
edge(const int &_to,const int &_dis,const int &_next){
to=_to,dis=_dis,next=_next;
}
}e[maxn<<1];
int head[maxn],k;
int f[maxn],dp[maxn];
int n,ans,deg[maxn];
inline int read(){
register int x(0),f(1); register char c(getchar());
while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
inline void add(const int &u,const int &v,const int &w){
e[k]=edge(v,w,head[u]),head[u]=k++;
}
void dfs(int u,int pre){
dp[u]=f[u]=0;
for(register int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(v==pre) continue;
dfs(v,u);
if(deg[v]==1) f[u]+=e[i].dis;
else f[u]+=min(f[v],e[i].dis);
}
}
void dfs2(int u,int pre){
for(register int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(v==pre) continue;
if(deg[u]==1) dp[v]=f[v]+e[i].dis;
else dp[v]=f[v]+min(dp[u]-min(f[v],e[i].dis),e[i].dis);
dfs2(v,u);
}
}
int main(){
int t=read();
while(t--){
memset(head,-1,sizeof head),k=0;
memset(deg,0,sizeof deg);
n=read(),ans=0;
for(register int i=1;i<n;i++){
int u=read(),v=read(),w=read();
add(u,v,w),add(v,u,w);
deg[u]++,deg[v]++;
}
dfs(1,0);
dp[1]=f[1],dfs2(1,0);
for(register int i=1;i<=n;i++) ans=max(ans,dp[i]);
printf("%d
",ans);
}
return 0;
}