樹的重心POJ 1655樹的最長(zhǎng)路徑最遠(yuǎn)點(diǎn)對(duì)POJ 1985樹的最大獨(dú)立集POJ 2342
對(duì)于一棵n個(gè)結(jié)點(diǎn)的無(wú)根樹，找到一個(gè)點(diǎn)，使得把樹變成以該點(diǎn)為根的有根樹時(shí)，最大子樹的結(jié)點(diǎn)數(shù)最小，該點(diǎn)即為重心。換句話說(shuō)，刪除這個(gè)點(diǎn)后最大連通塊（一定是樹）的結(jié)點(diǎn)數(shù)最小。
一道典型的求樹的重心的題目，用dfs實(shí)現(xiàn) 用數(shù)組dp[i]記錄i的最大子樹的大小，son[i]記錄兒子的個(gè)數(shù) 樹的重心即為所有節(jié)點(diǎn)中最大子樹大小最小的節(jié)點(diǎn)
#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]; 樹的最長(zhǎng)路徑（最遠(yuǎn)點(diǎn)對(duì)）樹形DP的板子題 不斷dfs更新出以每個(gè)點(diǎn)為根節(jié)點(diǎn)最遠(yuǎn)及次遠(yuǎn)的長(zhǎng)度，輸出長(zhǎng)度和的最大值即可
#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;}對(duì)于每一個(gè)節(jié)點(diǎn)有兩種情況，去或者不去，可用二維狀態(tài)表示 若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;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
