CCPC2017 湘潭邀请赛 H Highway（树的直径）

Highway

In ICPCCamp there were n towns conveniently numbered with 1,2,…,n connected with (n−1) roads. The i-th road connecting towns ai and bi has length ci. It is guaranteed that any two cities reach each other using only roads.

Bobo would like to build (n−1) highways so that any two towns reach each using only highways. Building a highway between towns x and y costs him δ(x,y) cents, where δ(x,y) is the length of the shortest path between towns x and y using roads.

As Bobo is rich, he would like to find the most expensive way to build the (n−1) highways.

Input

The input contains zero or more test cases and is terminated by end-of-file. For each test case:

The first line contains an integer n. The i-th of the following (n−1) lines contains three integers ai, bi and ci.

$1≤n≤10^{5}$
$1≤a_{i},b_{i}≤n$
$1≤c_{i}≤10^{8}$
The number of test cases does not exceed 10.

Output

For each test case, output an integer which denotes the result.

Sample Input

Sample Output

19
15

链接

湘大OJ日常抽风，这是叉姐的网站，https://post.icpc.camp/d/683-2017

题意

给定一个点数为n的图，给定n-1条边及其权值，让你重新选择n-1条边使其联通并且权值和最大，新边的权值为原来两点间最短路径

题解

树的直径问题。

两次bfs求得树的最长直径，并得到直径的两个端点，然后加上其他所有点到两端点的最大距离。

这道题就是让你求对于i点，距离这个点最远的点，我们容易想到用dp写，但是这样明显有一个问题，就是会不会有重复的，还需要标记一下，有点麻烦，但是其实我们不用担心这个，接下来我们引入树的直径的概念，并给出一些推论，树的直径是指树上权值和最大的路径（最简单路径，即每一个点只经过一次），存在结论：对于树上的任意一个一个节点，距离这个节点最远的距离一定是直径的两个端点，给出证明：假设当前点为u，直径端点为s，t。
第一种情况：u在直径上，那么显然终点在端点上，我们用反证法证明，假设终点不在端点上，设其为e，那么存在dis(u-e)大于dis(u-s) 即存在dis(u-e)+dis(u-t)>dis(u-s)+dis(u-s)=dis(u-t)矛盾
第二种情况：u不在直径上
第一种情况，当u的最长路与直径相交，设交点为x，此时存在，dis(u-x)+dis(x-e)>dis(u-x)+dis(x-s) 即dis(u-x)+dis(x-e)+dis(x+t)>dis(u-x)+dis(x-s)+dis(x-t) = dis(u-x)+dis(s-t)矛盾，
第二种情况：不相交，这种麻烦点懒得推了
说一下求端点的技巧，选取任意一点开始dfs，去到的权值和最大的即为端点之一，然后从这个端点开始出发去寻找另一个端点
参考：https://blog.csdn.net/w571523631/article/details/72403849

代码

// 没交，仅供参考

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 100010;
ll dist1[maxn], dist2[maxn];
int head[maxn];
bool vis[maxn];
int n, cnt;

struct Edge
{
    int to, next, w;
}edge[maxn];

void addedge(int u, int v, int w)
{
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void dfs(int u, ll d, ll dist[])
{
    dist[u] = d;
    vis[u] = true;
    for (int i = head[u]; i != -1; i = edge[i].next)
    {
        if (!vis[edge[i].to])
            dfs(edge[i].to, d + edge[i].w, dist);
    }
}

int main()
{
    int u, v, w, d1, d2;
    ll sum, maxdist;
    while(scanf("%d", &n) != EOF)
    {
        memset(head, -1, sizeof(head));
        cnt = 0;
        for (int i = 0; i < n - 1; ++i)
        {
            scanf("%d%d%d", &u, &v, &w);
            addedge(u, v, w);
            addedge(v, u, w);
        }
        memset(vis, 0, sizeof(vis));
        maxdist = 0;
        dfs(1, 0, dist1); // 任一点开始bfs得到端点d1
        for (int i = 1; i <= n; ++i)
        {
            if (dist1[i] > maxdist)
            {
                maxdist = dist1[i];
                d1 = i;
            }
        }
        memset(vis, 0, sizeof(vis));
        maxdist = 0;
        dfs(d1, 0, dist1); // 从端点d1开始得到端点d2
        for (int i = 1; i <= n; ++i)
        {
            if (dist1[i] > maxdist)
            {
                maxdist = dist1[i];
                d2 = i;
            }
        }
        sum = dist1[d2];
        memset(vis, 0, sizeof(vis));
        dfs(d2, 0, dist2);
        for (int i = 1; i <= n; ++i)
        {
            if (i != d1 && i != d2)
                sum += max(dist1[i], dist2[i]); // 到两个端点中距离最大的
        }
        printf("%lld\n", sum);
    }
    return 0;
}

对图的链式前向星有了更多的了解，以及树的直径问题。

The end.
2018-05-06 星期天