link

题意

有 $n$ 个点和 $m$ 条边，每条边连接两个节点，长度为 $T_i$，且保证输入是一个森林。让我们将每个森林用一条长度为 $L$ 的边连接，使得连接后的树的直径最短。

思路分析

我们可以用每颗树的直径的中点相连，这样可以使得直径最小，因为如果一颗树不是由直径的中点与其他树相连，那么就可以从直径的另一个端点出发，就会大于用中点相连的情况。

我们可以观察题目给出的图片：

答案是 $18$，是由半径最大的树的半径与半径第二大的树的半径相连得出的。

实际上，我们可以把这张图看成是一张菊花图，于是也可以看成是由其他树的中点与半径最大的树的中点相连形成的一张菊花图。

于是答案可以分三种情况讨论：

• 原本森林中的最大直径。也就是最大树的直径的中点与其它树的直径的中点相连后，并没有另一条直径大于原本的半径最大的树的直径。
• 最长的半径与次长的半径的和加上 $L$。有题目给出的样例可以看出，如果每颗树都直接与最大半径的树相连，答案有可能就为最大半径加上次大半径相连之后的长度。前提条件是这个森林必须有两棵及以上的树。
• 次长半径与第三长半径的和加上两倍 $L$。我们不难从图片中看出，第二大的树和第三大的树相连需要两条边，所以当 $L$ 足够大且最长半径与次长半径的和与次长半径与第三长半径的和之差较小时，次长半径与第三长半径相连之后的长度可能成为答案。前提条件是这棵森林必须有三棵及以上的树。

于是我们就可以求出每颗树的半径，最后再排个序，分情况讨论即可。那么怎样区分开每颗树呢？我们可以用染色的方式来维护，也可以用并查集维护。我这里只展示用并查集的方法。

Code

#include<bits/stdc++.h>
using namespace std;
struct node {
    int v, w;
};
int n, m, l, cnt, ans;
int pos;
int d[100010], dis[100010], pre[100010], fa[100010];
vector<node> q[100010];
int find(int u) {
    if (fa[u] == u) return u;
    return fa[u] = find(fa[u]);
} //并查集 
bool cmp(int a, int b) {
    return a > b;
} //排序函数 
void dfs(int u, int fa) {
    pre[u] = fa; //记录前缀 
    if (dis[u] >= dis[pos]) {
        pos = u;
    } //为什么 >= 时也要更新呢？因为可能有孤立点，为了防止孤立点的直径为初始最大值 
    for (int i = 0; i < q[u].size(); i++) {
        int v = q[u][i].v, w = q[u][i].w;
        if (v == fa) continue;
        dis[v] = dis[u] + w; //注意每条边都有边权，所以这里加上边权 
        dfs(v, u);
    }
    return;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0); //超级输入输出流 
	cin >> n >> m >> l;
    for (int i = 1; i <= n; i++) fa[i] = i; //初始化 
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        u++, v++; //题目节点编号从 0 开始，我习惯从下标为 1 开始的 qwq 
        q[u].push_back({v, w});
        q[v].push_back({u, w}); //存图 
        fa[find(u)] = find(v); //变成同一棵树 
    }
    for (int i = 1; i <= n; i++) {
        if (fa[i] == i) {
            dfs(i, 0);
            dis[pos] = 0;
            dfs(pos, 0); //求直径 
            d[++cnt] = INT_MAX; // d[cnt] 为这棵树的半径 
            for (int j = pos; j; j = pre[j]) { //枚举到直径上的每一个点
                d[cnt] = min(d[cnt], max(dis[j], dis[pos] - dis[j]));
            } //因为题目有边权，所以半径不能直接取 (dis[pos] + 1) / 2 
            //于是我们枚举到每一个点，求出它距离直径端点远的那一边，如果它是半径，那么它距离直径的两个端点的距离就会比较平均，相比于其他点距离直径端点更远的那一边就会更小。
			//就好比与你分东西，如果这个人少分了 1 个，那么另一个人就会多分一个
			//反之如果两个人平分，那么就相当于把第一种情况的另一个人少分了一个，这个人就补齐了差值，自然会比第一种情况里另一个人分到的要少了。 
            ans = max(ans, dis[pos]); //更新第一种情况的答案，就是这里被卡了 114514 次 qwq 
            // cout << pos << ' ' << dis[pos] << endl;
            // ans = max(ans, dis[pos]);
            pos = 0; //记得把直径的端点重置，防止它影响其他树的答案 
        }
    }
    sort(d + 1, d + cnt + 1, cmp); //排序 
    if (cnt >= 2) {
        ans = max(ans, d[1] + d[2] + l);
    }
    if (cnt >= 3) {
        ans = max(ans, d[2] + d[3] + 2 * l);
    } //分类讨论 
    cout << ans << endl; //输出 
	return 0;
}

愉快的 AC