BZOJ1509: [NOI2003]逃学的小孩(树的直径)-白红宇

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

阅读量：5949 次

发布时间：2019-06-19

本文共 1961 字，大约阅读时间需要 6 分钟。

Time Limit: 5 Sec Memory Limit: 64 MB

Submit: 1126 Solved: 567

[][][]

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

HINT

Source

这题比较naive吧。。

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

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

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

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

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #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());}

转载地址：http://jwsxx.baihongyu.com/

你可能感兴趣的文章