题解：P5895 [IOI 2013] dreaming 梦想

· · 题解

这个题对我来说最大的帮助在于并查集，而非树的直径（神秘同学并查集 find 写错而且父亲数组不初始化）。

思路

题意就是给你一个森林，用一些边将所有树连起来，求在所有方案中最小的直径长度。

如果自己手玩数据，就可以发现最短的直径所构造出来的图是所有树全连接到一棵树上。

像极了某种能卡 SPFA 的图。

就可以发现这是个菊花图。

那么我们就可以求出每一棵树的直径，找到其半径（即一棵树上所有点的最远距离中最短的长度）。对其进行排序从大到小排序，就可以发现这个题最后的答案无非只有三种情况：

  1. 就是原本所有树的直径中的最长直径。

  2. 最大的半径长 + 第二大的半径长 +L。

  3. 第二大的半径长 + 第三大的半径长 +2\times L。

再用并查集维护一下，取最大，这个题就被我们搞定了！

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,l,L,a,pre[100005],fa[100005],d[100005],dis[100005],cnt,ans;
vector<pair<int,int> > e[100005];
int fnd(int x)
{
    return x==fa[x]?x:fa[x]=fnd(fa[x]); // 并查集查找。
}
void dfs(int u,int f)
{
    pre[u]=f; // 记录每一个点的前驱，后面求半径时要用。
    if(dis[u]>=L) L=dis[u],a=u; // 更新直径长度。
    for(int i=0;i<e[u].size();i++)
    {
        int v=e[u][i].first;
        int w=e[u][i].second;
        if(v==f) continue;
        dis[v]=dis[u]+w; // 更新长度数组 dis。
        dfs(v,u); // 继续往下搜索。
    }
    ans=max(ans,L); // 记录所有树中最长的直径，对应情况 1。
}
void solve(int x)
{
    L=0; // 初始化直径。
    dfs(x,0); // 从根节点开始搜索。
    dis[a]=0; // 重置 dis 数组。
    L=0; // 重置直径。
    dfs(a,0);
    int tmp=1e9;
    for(int i=a;i;i=pre[i]) tmp=min(tmp,max(dis[i],L-dis[i])); // 对于直径上的所有点，比较其与两个端点长度进行比较取最大值，记录所有点中最大值的最小值。 
    d[++cnt]=tmp; // 记录每棵树的半径。 
}
bool cmp(int a,int b)
{
    return a>b; 
}
signed main()
{
    cin>>n>>m>>l;
    for(int i=1;i<=n;i++) fa[i]=i; // fa 数组初始化。 
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w; // 读入每条边。 
        u++; // 特别注意：题目中下是从 0 开始的，如果我们用 1 开始，则输入的编号要 +1。 
        v++;
        e[u].push_back({v,w});
        e[v].push_back({u,w}); // 存边。 
        fa[fnd(u)]=fnd(v); // 合并。 
    }
    for(int i=1;i<=n;i++)
    {
        if(fa[i]==i) solve(i); // 如果是树的根节点，那么进行搜索并求半径 。 
    }
    sort(d+1,d+cnt+1,cmp); // 将半径由大到小排序。 
    if(cnt>=2) ans=max(ans,d[1]+d[2]+l); // 对应情况 2。 
    if(cnt>=3) ans=max(ans,d[2]+d[3]+2*l); // 对应情况 3。 
    cout<<ans; // 取最大的，输出。 
    return 0;
}