树形DP

2019-11-10 18:05:16

字体：大中小

来源：转载

供稿：网友

树的重心POJ 1655树的最长路径最远点对POJ 1985树的最大独立集POJ 2342

树的重心

对于一棵n个结点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的结点数最小，该点即为重心。换句话说，删除这个点后最大连通块（一定是树）的结点数最小。

POJ 1655

一道典型的求树的重心的题目，用dfs实现用数组dp[i]记录i的最大子树的大小，son[i]记录儿子的个数树的重心即为所有节点中最大子树大小最小的节点

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define L 20010using namespace std;struct node{ int nxt, to;} a[L << 1];int n, T, u, v, head[L], cnt, son[L], siz, ans, dp[L];inline void add(int x, int y) { a[++cnt].nxt = head[x]; a[cnt].to = y; head[x] = cnt;}inline void dfs(int s, int fa) { dp[s] = 0, son[s] = 1; for (int i = head[s]; i; i = a[i].nxt) { int u = a[i].to; if (u == fa) continue; dfs(u, s); dp[s] = max(dp[s], son[u]); son[s] += son[u]; } dp[s] = max(dp[s], n - son[s]);}int main() { scanf("%d", &T); while (T--) { memset(a, 0, sizeof(a)); memset(head, 0, sizeof(head)); memset(dp, 0, sizeof(dp)); memset(son, 0, sizeof(son)); cnt = 0; scanf("%d", &n); for (int i = 1; i < n; ++i) { scanf("%d %d", &u, &v); add(u, v), add(v, u); } dfs(1, 0); ans = 1, siz = dp[1]; for (int i = 2; i <= n; ++i) if (dp[i] < siz) ans = i, siz = dp[i]; PRintf("%d %d/n", ans, siz); } return 0;}

树的最长路径（最远点对）

POJ 1985

树形DP的板子题不断dfs更新出以每个点为根节点最远及次远的长度，输出长度和的最大值即可

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define L 1000010using namespace std;struct node{ int nxt, to; long long l;} e[L];int n, m, a, b, head[L], cnt;long long c, dp1[L], dp2[L], ans;char pd[3];inline void add(int a, int b, long long d) { e[++cnt].nxt = head[a]; e[cnt].to = b; e[cnt].l = d; head[a] = cnt;}inline void dfs(int x, int fa) { for (int i = head[x]; i; i = e[i].nxt) { int u = e[i].to; if (u == fa) continue; dfs(u, x); if (dp1[x] < dp1[u] + e[i].l) dp2[x] = dp1[x], dp1[x] = dp1[u] + e[i].l; else dp2[x] = max(dp2[x], dp1[u] + e[i].l); } ans = max(ans, dp1[x] + dp2[x]);}int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= m; ++i) { scanf("%d %d %lld %s", &a, &b, &c, pd); add(a, b, c), add(b, a, c); } dfs(1, 0); printf("%lld/n", ans); return 0;}

树的最大独立集

POJ 2342

对于每一个节点有两种情况，去或者不去，可用二维状态表示若i去了，则i的儿子不能去，dfs更新值即可

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define L 6000 + 10using namespace std;int n, a, b, root, fa[L], vis[L], dp[L][2];inline void dfs(int x) { vis[x] = 1; for (int i = 1; i <= n; ++i) if (fa[i] == x && !vis[i]) { dfs(i); dp[x][1] += dp[i][0]; dp[x][0] += max(dp[i][1], dp[i][0]); }}int main() { while (scanf("%d", &n) == 1){ for (int i = 1; i <= n; ++i) scanf("%d", &dp[i][1]); root = 0; while(scanf("%d %d", &a, &b) && a && b) fa[a] = b, root = b; memset(vis, 0, sizeof(vis)); dfs(root); printf("%d/n", max(dp[root][1], dp[root][0])); } return 0;}

上一篇：eclipse tomcat add and remove工程异常

下一篇：洛谷