确定了根节点之后,其最大流量就是所有子节点最大流量之和,其子节点的最大流量有两个限制:
- 子节点到根节点的边的容量限制
- 子节点到其子节点的流量限制
两个限制的最小值就是该条路径的最大流量
如果把每个点作为根节点遍历一遍的话,时间复杂度就是:$\mathcal O(n^2)$,在 $N \le 2\times 10^5$ 的数据范围之下肯定是不允许的
换根DP
一般思路:
- 自底向上维护某些信息
- 自项向下进行DP状态转移
若以 $1$ 号点作为根节点,如何求其最大流量 ?
我们维护一个数组d[u]
:表示从u
往下流的最大流量
枚举其所有子节点,对于某个子节点s
的最大流量,u
流向这个子节点的路径的最大流量就是,min(d[s], w[i])
,所有流向子节点的路径的最大流量的和就是u
的最大流量 —— 自底向上:由子节点的状态向父节点转移
因此所有叶子节点的流量都要设为正无穷
INF
,否则叶子节点流量为0
的状态会一直转移到根节点
那么如何确定除了根节点之外的节点的最大流量 ?
确定了根节点之后,除了根节点之外的所有节点j
的水流路径可以分为两类:
- 从该点往下流:
d[j]
- 从该点到其父节点往上流:
min(d[fa[j]] - 往 j 流的流量, w[i])
其中的第 $2$ 类,从该点往其父节点流的最大流量,等价于与其父节点往下流的最大流量 $-$ 从父节点往该节点流的最大流量,由于还有该点到其父节点的边的限制,因此还需要与w[i]
取最小值
( 分类依据本质上和 计算机 一致 )
这两个流量的和就是节点j
的最大流量
最后依次枚举每个点,取最大值就是此题答案
时间复杂度:$\mathcal O(n)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010, M = N << 1, INF = 1e9;
int n;
int h[N], w[M], e[M], ne[M], idx;
int d[N], f[N]; // d[] 表示往下走的流量 f[] 表示总共的流量
int deg[N]; // 每个点的度数 判断是否是叶子节点
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs_d(int u, int fa)
{
if (deg[u] == 1) d[u] = INF; // 叶子节点无法往下流 流量为 INF
else
{
d[u] = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
d[u] += min(w[i], dfs_d(j, u));
// d[u] 表示所有子节点的流量 与 u 到该子节点的边的流量限制的 最小值
// 所有子节点的流量的和就是 d[u]
}
}
return d[u];
}
void dfs_f(int u, int fa)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
// 叶子节点 // 叶子节点的父节点 往该叶子节点的流量就是该条边的容量
if (deg[j] == 1) f[j] = min(w[i], f[u] - w[i]); // 注意和 w[i] 取 min
else
{
// 由于叶子节点的 d[j] 是 INF 所以需要分类
f[j] = d[j] + min(w[i], f[u] - min(d[j], w[i])); // 注意和 w[i] 取 min
dfs_f(j, u); // 只有不是叶子节点才往下递归计算其它节点
}
}
}
int main()
{
int T;
scanf("%d", &T);
while (T -- )
{
scanf("%d", &n);
// 注意清空
idx = 0;
for (int i = 1; i <= n; i ++ ) h[i] = -1;
for (int i = 1; i <= n; i ++ ) deg[i] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
deg[a]++, deg[b] ++ ;
}
// 选择一个度数 > 1 的点作为根节点!
int root = 1;
while (root <= n && deg[root] == 1) root ++ ;
if (root > n) // 如果所有点的度数均为 1,说明是只有两个点一条边 需要特判
{
cout << w[0] << endl;
continue;
}
dfs_d(root, -1);
f[root] = d[root];
dfs_f(root, -1);
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);
printf("%d\n", res);
}
return 0;
}