【POJ - 3585】:Accumulation Degree 树形DP + 二次扫描
2021/7/4 6:23:41
本文主要是介绍【POJ - 3585】:Accumulation Degree 树形DP + 二次扫描,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门
分析
系统的刷一下换根DP这个专题
首先如果我们固定一个根节点的话,可以在
O
(
n
)
O(n)
O(n)的复杂度内解决这个问题,但这道题是不定根,如果我们去一次枚举根的话,显然
O
(
n
2
)
O(n ^ 2)
O(n2)的复杂度是不合适的,那么我们怎么去优化呢
假设我们先
d
f
s
dfs
dfs一下这个棵树,假设根为
r
o
o
t
root
root,处理出
d
i
d_{i}
di数组表示以
i
i
i为根节点的子树中的最大流量是多少,那么以
r
o
o
t
root
root为根的答案就为
f
[
r
o
o
t
]
=
d
[
r
o
o
t
]
f[root] = d[root]
f[root]=d[root],然后再
d
f
s
dfs
dfs一下这棵树,
r
o
o
t
root
root的子节点
j
j
j的答案,就是以子节点
j
j
j构成的子树
d
i
d_{i}
di再加上流向父节点的流量,处理一下即可
代码
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #define dl(x) printf("%lld\n",x); #define di(x) printf("%d\n",x); using namespace std; const int N = 1e6 + 10; template<typename T>inline void read(T &a) { char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();} while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x; } int h[N], e[N], ne[N], w[N], idx; int n, d[N], in[N], f[N]; void init() { for (int i = 1; i <= n; i++) h[i] = -1, in[i] = 0; idx = 0; } void add(int x, int y, int z) { ne[idx] = h[x], e[idx] = y, w[idx] = z, h[x] = idx++; } void dfs(int u, int fa) { d[u] = 0; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa) continue; dfs(j, u); if (in[j] == 1) d[u] += w[i]; else d[u] += min(w[i], d[j]); } } void dfs_(int u, int fa) { for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == fa) continue; if (in[u] == 1) f[j] = d[j] + w[i]; else f[j] = d[j] + min(f[u] - min(d[j], w[i]), w[i]); dfs_(j,u); } } int main() { int T; read(T); while (T--) { read(n); init(); for (int i = 1; i < n; i++) { int x, y, z; read(x), read(y), read(z); add(x, y, z), add(y, x, z); in[x]++, in[y]++; } dfs(1, -1); f[1] = d[1]; dfs_(1, -1); int res = 0; for (int i = 1; i <= n; i++) res = max(res, f[i]); di(res); } return 0; }
这篇关于【POJ - 3585】:Accumulation Degree 树形DP + 二次扫描的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享