1207-大臣的旅费

#personal/blog

题目描述

关系

内容

很久以前， $T$ 王国空前繁荣。

为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。

为节省经费， $T$ 国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。

同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

$J$ 是 $T$ 国重要大臣，他巡查于各大城市之间，体察民情。

所以，从一个城市马不停蹄地到另一个城市成了 $J$ 最常做的事情。

他有一个钱袋，用于存放往来城市间的路费。

聪明的 $J$ 发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关。

具体来说，一段连续的旅途里，第 $1$ 千米的花费为 $11$ ，第 $2$ 千米的花费为 $12$ ，第 $3$ 千米的花费为 $13$ ，…，第 $x$ 千米的花费为 $x + 10$ 。

也就是说，如果一段旅途的总长度为 $1$ 千米，则刚好需要花费 $11$ ，如果一段旅途的总长度为 $2$ 千米，则第 $1$ 千米花费 $11$ ，第 $2$ 千米花费 $12$ ，一共需要花费 $11 + 12 = 23$ 。

$J$ 大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

输入格式

输入的第一行包含一个整数 $n$ ，表示包括首都在内的 $T$ 王国的城市数。

城市从 $1$ 开始依次编号， $1$ 号城市为首都。

接下来 $n - 1$ 行，描述 $T$ 国的高速路（ $T$ 国的高速路一定是 $n - 1$ 条）。

每行三个整数 $P_{i}, Q_{i}, D_{i}$ ，表示城市 $P_{i}$ 和城市 $Q_{i}$ 之间有一条双向高速路，长度为 $D_{i}$ 千米。

输出格式

输出一个整数，表示大臣 $J$ 最多花费的路费是多少。

数据范围

$1 \leq n \leq 10^{5}$ ,
$1 \leq P_{i}, Q_{i} \leq n$ ,
$1 \leq D_{i} \leq 1000$

输入样例：

输出样例：

问题分析

最初思路

暴力的方式是，遍历每一个节点，以每一个节点为 bfs 的开头，查找最远距离，最后得出答案。但是，这是超时的。

矛盾是没有固定一个起始位置。

有两种情况，一种是不经过首都，一种是经过首都的路径。麻烦的是后者，如果能够维护一个二维数组，用来记录每个节点到首都的距离，那么后者就解决了。

思路分析

这道题是树的直径，001-1072-树的最长路径。

执行流程设计

总结

代码实现

bfs

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct edge {
    int id, w;
};

const int N = 1e5 + 10;
int n;
vector<edge> h[N];
int dis[N];
bool st[N];

void bfs(int u) {
    queue<int> q;
    q.push(u);
    st[u] = true;
    dis[u] = 0;
    while (!q.empty()) {
        int c = q.front();
        q.pop();
        
        for (auto e: h[c]) {
            if (st[e.id]) continue;
            
            st[e.id] = true;
            
            dis[e.id] = dis[c] + e.w;
            
            q.push(e.id);
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        h[a].push_back({b, c});
        h[b].push_back({a, c});
    }
    
    bfs(1);
    
    int m = 1;
    for (int i = 1; i <= n; i++) 
        if (dis[i] > dis[m]) m = i;
    
    memset(st, 0, sizeof st);
    
    bfs(m);
    
    for (int i = 1; i <= n; i++) 
        if (dis[i] > dis[m]) m = i;
    
    ll s = dis[m];
    ll ans = (21 + s) * s / 2;
    printf("%lld", ans);
    return 0;
}

dfs

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct edge {
    int id, w;
};

const int N = 1e5 + 10;
int n;
vector<edge> h[N];
int dis[N];

void dfs(int u, int father, int distance) {
    dis[u] = distance;
    
    for (auto e: h[u]) {
        if (e.id != father) {
            dfs(e.id, u, e.w + distance);
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        h[a].push_back({b, c});
        h[b].push_back({a, c});
    }
    
    dfs(1, -1, 0);
    
    int m = 1;
    for (int i = 1; i <= n; i++) 
        if (dis[i] > dis[m]) m = i;
    
    dfs(m, -1, 0);
    
    for (int i = 1; i <= n; i++) 
        if (dis[i] > dis[m]) m = i;
    
    ll s = dis[m];
    ll ans = (21 + s) * s / 2;
    printf("%lld", ans);
    return 0;
}