SGU 149. Computer Network( 树形dp )
2024-10-12 04:46:34
题目大意:给N个点，求每个点的与其他点距离最大值
很经典的树形dp...很久前就想写来着...看了陈老师的code才会的...mx[x][0], mx[x][1]分别表示x点子树里最长的2个距离, dfs一遍得到. mx[x][2]表示从x的父亲到x的最长路径长度, 也是dfs一遍得到(具体看代码)。最后答案就是max(mx[x][0], mx[x][2]). 时间复杂度O(N)
--------------------------------------------------------------------------------------------
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 10009;
int N, mx[maxn][3];
struct edge {
int to, w;
edge* next;
} E[maxn << 1], *pt = E, *head[maxn];
void AddEdge(int u, int v, int w) {
pt->to = v; pt->w = w; pt->next = head[u]; head[u] = pt++;
}
void Init() {
scanf("%d", &N);
for(int i = 1; i < N; i++) {
int t, w; scanf("%d%d", &t, &w); t--;
AddEdge(i, t, w);
AddEdge(t, i, w);
}
}
inline void upd(int x, int t) {
if(mx[x][1] < t)
mx[x][1] = t;
if(mx[x][0] < mx[x][1])
swap(mx[x][0], mx[x][1]);
}
void DFS0(int x, int fa = -1) {
mx[x][0] = mx[x][1] = 0;
for(edge* e = head[x]; e; e = e->next) if(e->to != fa) {
DFS0(e->to, x);
upd(x, mx[e->to][0] + e->w);
}
}
void DFS1(int x, int fa = - 1) {
for(edge* e = head[x]; e; e = e->next) if(e->to != fa) {
mx[e->to][2] = mx[x][2] + e->w;
if(mx[e->to][0] + e->w == mx[x][0])
mx[e->to][2] = max(mx[e->to][2], mx[x][1] + e->w);
else
mx[e->to][2] = max(mx[e->to][2], mx[x][0] + e->w);
DFS1(e->to, x);
}
}
int main() {
Init();
DFS0(0);
DFS1(mx[0][2] = 0);
for(int i = 0; i < N; i++)
printf("%d\n", max(mx[i][2], mx[i][0]));
return 0;
}
--------------------------------------------------------------------------------------------
149. Computer Network
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
memory limit per test: 4096 KB
input: standard input
output: standard output
output: standard output
A school bought the first computer some time ago. During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know for each computer number Si - maximum distance, for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information.
Input
There is natural number N (N<=10000) in the first line of input, followed by (N-1) lines with descriptions of computers. i-th line contains two natural numbers - number of computer, to which i-th computer is connected and length of cable used for connection. Total length of cable does not exceed 10^9. Numbers in lines of input are separated by a space.
Output
Write N lines in output file. i-th line must contain number Si for i-th computer (1<=i<=N).
Sample test(s)
Input
3
1 1
1 2
1 1
1 2
Output
2
3
3
3
3
| Author: | Andrew V. Lazarev, Michael R. Mirzayanov |
| Resource: | Saratov Subregional School Team Contest, 2002 |
| Date: | Fall, 2002 |
最新文章
- AJAX操作数据
- 截取UTF-8编码的汉字，最后一个字出现乱码的问题
- css3中transition和display的坑
- [python实现设计模式]-3.简单工厂模式-触宝开放平台
- java web 学习 --第五天（Java三级考试）
- 主机与虚拟机通信：以主机VS2010连接虚拟机MySql为例
- php-fpm 进程管理
- lnmp下配置虚拟主机
- Linux Kernel ‘exitcode_proc_write()’函数本地缓冲区溢出漏洞
- 窥探Unity5渲染内部之解析UnityShaderVariables.cginc
- Javascript 获取url参数，hash值 ，cookie
- Ubuntu12.10无法安装openssh-server[已解决]
- WTL 设置 SDI 主窗口初始大小的方法
- 搭建自己的CA服务 - OpenSSL CA 实战
- ava 8中的新功能特性
- 读取Excel中数据
- C++了解free和delete
- 02 爬虫数据解析之re,xpath,beautifulsoup
- springboot分环境打包（maven动态选择环境）
- Python学习-39.Python中的生成器