BZOJ1509: [NOI2003]逃学的小孩(树的直径)

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 1126  Solved: 567

[Submit][Status][Discuss]

Description

Input

第一行是两个整数N(3  N  200000)和M,分别表示居住点总数和街道总数。以下M行,每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti(1Ui, Vi  N,1  Ti  1000000000),表示街道i连接居住点Ui和Vi,并且经过街道i需花费Ti分钟。街道信息不会重复给出。

Output

仅包含整数T,即最坏情况下Chris的父母需要花费T分钟才能找到Chris。

Sample Input

4 3 1 2 1 2 3 1 3 4 1

Sample Output

4

HINT

Source

这题比较naive吧。。

不过我一开始以为C是给出的。

很显然$AB$一定是树的直径。

敲完了才发现C是不固定的以为自己白写了。

但实际上只需要求出直径的端点到每个点的距离,然后在小的里面取最大就好了

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#define int long long 
using namespace std;
const int INF = 1e9 + 10, MAXN = 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M;
struct Edge {
    int u, v, w, nxt;
}E[MAXN];
int head[MAXN], num = 1;
inline void AddEdge(int x, int y, int z) {
    E[num] = (Edge) {x, y, z, head[x]};
    head[x] = num++;
}
int dis[MAXN], mx, mxdis;
void dfs(int x, int fa) {
    for(int i = head[x]; i != -1; i = E[i].nxt) {
        if(E[i].v == fa) continue;
        dis[E[i].v] = dis[x] + E[i].w;
        dfs(E[i].v, x);
        if(dis[E[i].v] > mxdis) mxdis = dis[E[i].v], mx = E[i].v;
    }
}
int Node1, Node2, dis1[MAXN], dis2[MAXN];
int GetAns() {
    memset(dis, 0, sizeof(dis)); dfs(Node1, 0);
    for(int i = 1; i <= N; i++) dis1[i] = dis[i];
    memset(dis, 0, sizeof(dis)); dfs(Node2, 0);
    for(int i = 1; i <= N; i++) dis2[i] = dis[i];
    int rt = 0;
    for(int i = 1; i <= N; i++)
        rt = max(rt, min(dis1[i], dis2[i]));
    return rt;
}
main() { 
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    memset(head, -1, sizeof(head));
    N = read(); M = read();
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read(), z = read();
        AddEdge(x, y, z);
        AddEdge(y, x, z);
    }
    dfs(1, 0); Node1 = mx;
    memset(dis, 0, sizeof(dis)); mxdis = 0;
    dfs(mx, 0); Node2 = mx;
    int ans = dis[mx];
    printf("%I64d", ans + GetAns());
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏强仔仔

freemarker常见的一些用法(一)

今天给大家介绍一下freemarker基本用法,例如:if、 list、 判断是否为空、获取值等等之类的。 在使用之前要先在模板中设置值,这里我使用的是Spri...

39790
来自专栏chenjx85的技术专栏

leetcode-342-Power of Four

25440
来自专栏HansBug's Lab

1901: Zju2112 Dynamic Rankings

1901: Zju2112 Dynamic Rankings Time Limit: 10 Sec  Memory Limit: 128 MB Submit: ...

29360
来自专栏DT乱“码”

ClassPathXmlApplicationContext方式读取配置文件

public interface BeanFactory {   public Object getBean(String id); }   //实现类Clas...

22450
来自专栏张善友的专栏

在Entity Framework 中执行T-sql语句

从Entity Framework  4开始在ObjectContext对象上提供了2个方法可以直接执行SQL语句:ExecuteStoreQuery<T> 和...

245100
来自专栏HansBug's Lab

2243: [SDOI2011]染色

2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MB Submit: 3113  Solved...

32490
来自专栏jeremy的技术点滴

写py2、py3兼容的代码

1K80
来自专栏图形学与OpenGL

WebGL三角形平移变换(矩阵方式)

37910
来自专栏一个会写诗的程序员的博客

第12章 元编程与注解、反射第12章 元编程与注解、反射

反射(Reflection)是在运行时获取类的函数(方法)、属性、父类、接口、注解元数据、泛型信息等类的内部信息的机制。这些信息我们称之为 RTTI(Run-T...

11020
来自专栏恰童鞋骚年

.NET中那些所谓的新语法之一:自动属性、隐式类型、命名参数与自动初始化器

开篇:在日常的.NET开发学习中,我们往往会接触到一些较新的语法,它们相对以前的老语法相比,做了很多的改进,简化了很多繁杂的代码格式,也大大减少了我们这些菜鸟码...

9120

扫码关注云+社区

领取腾讯云代金券