洛谷P1399 [NOI2013] 快餐店题解

题目链接：P1399 [NOI2013] 快餐店

题意：

cxy 打算在城市 C 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，cxy 希望快餐店的地址选在离最远的顾客距离最近的地方。

快餐店的顾客分布在城市 C 的 \(N\) 个建筑中，这 \(N\) 个建筑通过恰好 \(N\) 条双向道路连接起来，不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。cxy 的快餐店可以开设在任一建筑中，也可以开设在任意一条道路的某个位置上（该位置与道路两端的建筑的距离不一定是整数）。

现给定城市 C 的地图（道路分布及其长度），请找出最佳的快餐店选址，输出其与最远的顾客之间的距离。

输入格式：

第一行包含一个整数 \(N\)，表示城市 C 中的建筑和道路数目。

接下来 \(N\) 行，每行 \(3\) 个整数，\(A_i,B_i,L_i\)（\(1\leq i\leq N\)，\(L_i>0\)），表示一条道路连接了建筑 \(A_i\) 与 \(B_i\)，其长度为 \(L_i\)。

输出格式：

输出仅包含一个实数，四舍五入保留恰好一位小数，表示最佳快餐店选址距离最远用户的距离。

注意：你的结果必须恰好有一位小数，小数位数不正确不得分。

数据范围：

对于 \(100\%\) 的数据，\(1\leq N\leq 10^5\)，\(1\leq L_i \leq 10^9\)。

注意到 \(n\) 个点 \(n\) 条边的连通图，显然这是一棵基环树

对于原图是一棵树的情况，显然我们选择树的一个重心放快餐店。

那么这个基环树怎么做呢？不妨假设这个快餐店放在 \(x\) 的位置。

不难发现，最优方案中， \(x\) 一定存在至少两个等距的最远点。

证明：考虑反证法。

如果 \(x\) 仅存在一个最远点 \(y\) ，记 \(\operatorname{dis}(x,y) = d\) 。那么我们将 \(x\) 向 \(y\) 移动 \(\epsilon(\epsilon > 0)\)

则 \(d^{\prime} = d - \epsilon < d\) ，而到其它点的距离依然不超过 \(d\) 。与最优方案矛盾。\(\square\)

不失一般性，设这两个等距的最远点为 \(a,b\) ，则有以下几种情况：

事实上，如果存在大于两个最远点

若他们在同一个外向树内，则任取两个结点。否则，取任意两个不在同一外向树里的结点。

\(a,b\) 在基环树 \(C\) 的同一个外向树 \(T\) 上。（这里的外向树就是环上挂着的那些树）

对于这种情况，有 \(x \in T\) 。

证明：若 \(x \not\in T\) ，则我们可以将 \(x\) 向 \(\mathtt{rt}(T)\) 移动 \(\epsilon\) ，

若到最远点的距离没有变小，则说明存在其他的最远点 \(\{v_i\}\) 且 \(v_i \not\in T\) 。故这种情况不存在。

因此我们可以假设 \(C\setminus T\) 中不存在最远点，则当 \(x \in T\) 时存在最优解。
\(a,b\) 在不同的外向树上。

该情况下 \(a \leadsto x \leadsto b\) 的路径一定经过 \(C\) 的环，但是显然不会经过整个环。

更详细地，我们设这条路径为 \(a \leadsto p \leadsto x \leadsto q \leadsto b\) ，其中 \(p,q\) 为环上的“接口”。

则 \(a \leadsto p\) ，\(q \leadsto b\) 分别对应 \(a,b\) 所在外向树从根开始的最深路径。

但是我们怎么知道 \(p \leadsto x \leadsto q\) 经过了哪条边呢？答案是枚举环上的边，然后断环为链。

对于以上的两种情况，去一个最大值/2就行了。

那么具体该如何实现呢。

对于第一种情况，我们可以先跑一遍 \(\mathtt{dfs}\) 找到环上的结点

记录一下环上的结点是哪些，然后我们对于每个外向树都跑一遍dp即可。

具体地，设 \(f_i\) 表示 \(i\) 所在的外向树中深度最大的结点的深度，然后一边转移一边更新答案即可。

对于第二种情况，就比较麻烦了。记环 \(\Psi = \langle c_1,c_2,\dots c_k\rangle\) 。

设 \(F_i\) 表示断掉边 \((c_1,c_k)\) 后前 \(i\) 棵外向树到 \(c_1\) 的最长路径，则 \[ F_1 = f_{c_1} \\[6pt] F_i = \max\left\{F_{i-1},~ f_{c_i} + \mathrm{dis}(c_1,c_i)\right\} \] 设 \(G_i\) 表示断掉边 \((c_1, c_k)\) 后前 \(i\) 棵外向树与 \(i-1\) 个环上连接边构成的新树的直径，则 \[ G_1 = 0 \\[6pt] G_i= \max\left\{ G_{i-1} , ~\max_{1\le j < i}\left\{f_{c_i} + f_{c_j} + \mathrm{dis}(c_i,c_j)\right\} \right\} \] 这个里面的 \(\max\) 有一种单调队列优化的感觉，实际是前缀和优化。

记 \(D_i = \sum_{j = 1}^{i} c_j\) ，则转移方程可以转化为 \[ G_i= \max\left\{ G_{i-1} , ~f_{c_i} + D_i + \max_{1\le j < i}\left\{f_{c_j}- D_j \right\} \right\} \] 而这个 \(f_{c_j} - D_j\) 仅与 \(j\) 有关，因此只需要一个变量来记录最大值即可。

同理，我们可以维护一个后缀的，即

设 \(F^{\prime}_i\) 表示断掉边 \((c_1,c_k)\) 后，后 \(i\) 棵外向树到 \(c_k\) 的最长路径； \(G^{\prime}_i\) 表示断掉边 \((c_1,c_k)\) 后，后 \(i\) 棵外向树与 \(i-1\) 个环上连接边构成的新树的直径。

转移方程基本上是一样的，就改一下范围还有 \(i+1\) 啥的就好了。

现在我们就可以枚举断哪条边了。首先断 \((c_1,c_k)\) 我们已经算出来了，就是 \(G_k = G^{\prime}_1\)

考虑断掉 \((c_i,c_{i+1})~(1 \le i < k)\) 后的情况。我们可以以直径是否经过 \((c_1,c_k)\) 分为两类：

不经过 \((c_1,c_k)\) ，则此时的答案就是两端的直径相加，即 \[ \max\{G_i,~G^{\prime}_{i+1}\} \]
经过 \((c_1,c_k)\) ，则此时的答案就是 \[ F_i + F^{\prime}_{i+1} + w(c_1,c_k) \]

于是一般情况的答案就是 \[ \max\{G_i,~G^{\prime}_{i+1},~F_i + F^{\prime}_{i+1} + w(c_1,c_k)\} \] 最后我们和之前的第一种情况、还有前面的 \(G_k\) 取个 \(\min\) （因为要最优方案啊，不要搞错了）

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n,tim,fy,mx=0,mn,cnt,ans,cur,sum,pos=1;
int f[N],head[N],fl[N],fr[N],gl[N],gr[N];
int dfn[N],fa[N],c[N],cfn[N],cw[N],dep[N];
struct Edge{ int u,v,w,next; }e[N * 2];
void addEdge(int u,int v,int w) { e[++pos] = {u,v,w,head[u]}; head[u]=pos; }
void dfsC(int u)
{
    dfn[u] = ++tim;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v;
        if(!dfn[v])
        {
            fa[v] = u; dep[v] = dep[u] + e[i].w; dfsC(v);
        }else if(v != fa[u] && dfn[v] > dfn[u])
        {
            for(; v!=u; v=fa[v]) c[++cnt] = v, cfn[v] = cnt,cw[cnt] = dep[v] - dep[fa[v]];
            c[++cnt] = u; cfn[u] = cnt; fy = e[i].w; 
        }
    }
}
void dfs(int u,int Fa)
{
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v;
        if(!cfn[v] && v != Fa)
        {
            dfs(v,u);
            up(ans, f[u] + f[v] + e[i].w);
            up(f[u], f[v] + e[i].w);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(1);
    cin >> n;
    for(int i=1,u,v,w; i<=n; i++)
    {
        cin >> u >> v >> w;
        addEdge(u,v,w); addEdge(v,u,w);
    }
    dfsC(1);
    for(int i=1; i<=cnt; i++) dfs(c[i],0);
    for(int i=1; i<=cnt; i++)
    {
        sum += cw[i-1]; cur = f[c[i]] + sum;
        up(fl[i] = fl[i-1], cur);
        up(gl[i] = gl[i-1], cur + mx);
        up(mx, f[c[i]] - sum);
    }
    sum = mx = 0;
    for(int i=cnt; i; i--)
    {
        sum += cw[i]; cur = f[c[i]] + sum;
        up(fr[i] = fr[i+1], cur);
        up(gr[i] = gr[i+1], cur + mx);
        up(mx, f[c[i]] - sum);
    }
    mn = gr[1];
    for(int i=1; i<cnt; i++)
        down(mn, max({ gl[i], gr[i+1], fl[i] + fr[i+1] + fy }));
    up(ans, mn);
    cout << (1.0 * ans / 2) << '\n';
    return 0;
}