首页 > 代码库 > [HDU2196]Computer（DP）
[HDU2196]Computer（DP）
传送门
题意
给出一棵树，求离每个节点最远的点的距离
思路
对于我这种菜鸡，真是难啊。
我们能够很简单的求出每个点到以它为根的子树的最远点的距离，dfs 即可。
设 f[i][0] 表示点 i 到以它为根的子树的最远点的距离
f[i][1] 表示点 i 到以它为根的子树的次远点的距离（一会会用到）
f[i][2] 表示 除去点 i 的子树后，点 i 到离它最远的点的距离
val 表示边权
那么 f[v][2] 怎么求？（u 表示 v 的父亲）
if(f[v][0] + val[i] == f[u][0]) f[v][2] = f[u][1] + val[i];
else f[v][2] = f[u][0] + val[i];
f[v][2] = std::max(f[v][2], f[u][2] + val[i]);
那么一个点 i 到它的最远点的距离即为——max( f[i][0], f[i][2])
代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define M(a, x) memset(a, x, sizeof(a)); 5 6 const int MAXN = 10005; 7 int n, cnt; 8 int head[MAXN], to[MAXN << 1], val[MAXN << 1], next[MAXN << 1], f[MAXN][3]; 9 bool vis[MAXN];10 11 inline void add(int x, int y, int z)12 {13 to[cnt] = y;14 val[cnt] = z;15 next[cnt] = head[x];16 head[x] = cnt++;17 }18 19 inline void dfs1(int u)20 {21 int i, v, dis1 = 0, dis2 = 0;22 vis[u] = 1;23 for(i = head[u]; i != -1; i = next[i])24 {25 v = to[i];26 if(!vis[v])27 {28 dfs1(v);29 if(f[v][0] + val[i] > dis1) dis2 = dis1, dis1 = f[v][0] + val[i];30 else if(f[v][0] + val[i] > dis2) dis2 = f[v][0] + val[i];31 }32 }33 f[u][0] = dis1;34 f[u][1] = dis2;35 }36 37 inline void dfs2(int u)38 {39 int i, v;40 vis[u] = 1;41 for(i = head[u]; i != -1; i = next[i])42 {43 v = to[i];44 if(!vis[v])45 {46 if(f[v][0] + val[i] == f[u][0]) f[v][2] = f[u][1] + val[i];47 else f[v][2] = f[u][0] + val[i];48 f[v][2] = std::max(f[v][2], f[u][2] + val[i]);49 dfs2(v);50 }51 }52 }53 54 int main()55 {56 int i, x, y;57 while(~scanf("%d", &n))58 {59 M(head, -1);60 M(f, 0);61 cnt = 0;62 for(i = 2; i <= n; i++)63 {64 scanf("%d %d", &x, &y);65 add(i, x, y);66 add(x, i, y);67 }68 M(vis, 0);69 dfs1(1);70 M(vis, 0);71 dfs2(1);72 for(i = 1; i <= n; i++) printf("%d\n", std::max(f[i][0], f[i][2]));73 }74 return 0;75 }
[HDU2196]Computer（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。