MENU

CCPC2017 湘潭邀请赛 H Highway(树的直径)

2018 年 05 月 06 日 • 阅读: 969 • 图论阅读设置

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

5
1 2 2
1 3 1
2 4 2
3 5 1
5
1 2 2
1 4 1
3 4 1
4 5 2

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 星期天