一、题目

题目描述

王国有\(n\)座城市与\(n\)条有长度的街道，保证所有城市直接或间接联通，我们定义王国的直径为所有点对最短距离中的最大值，现因财政危机需拆除一条道路并同时要求所有城市仍然联通，求所有拆除方案中王国直径的最小值

输入格式

第一行一个整数\(n\)，接下来\(n\)行每行三个整数\(u,v,w\)表示城市\(u,v\)之间有一条长度为\(w\)的道路

输出格式

一行一个答案，表示所有方案中直径最小值

二、题意

定义直径为任意两点间的最短距离的最大值。给出一棵基环树，问删去环上的一条边，使剩下的树的直径最小。问最小的直径是多少。

三、PROCESS OF THINKING

我刚开始的时候在想怎么选择删的边才最优，后来想了一个上午发现好像行不通。所以我往枚举删除哪条边，然后快速求出此时的树的直径这方面想。

其中有一点可以确定，就是每个环上的点对应的树是不变的。

应该可以想到求出每个环上的点到其树中的最长链。然后通过环来合并这些链。

考虑环上的点，首先我们枚举只能从\(x\)开始顺时针走（相当于把\(x\)连向前面的点的边删掉）。设\(f_i\)为\(i\)这个点对应的链长，\(sum_i\)为\(i\)到\(x\)的距离。

由此可以得出一条路径可以表示为\[f_i+f_j+sum_j-sum_i\]，即为\[f_i-sum_i+sum_j+f_j\]。

而对于每种情况我们要求的是最长的路径。故只要\(f_i-sum_i\)最大，\(f_j+sum_j\)最大就行了。用两个set维护就好了。

至于万一选择的两个点\(i\)，\(j\)的相对位置的问题，我也思考了一下（可能是我太弱了）。

我们假设\(i\)在\(j\)后面，而我们选择了\(i\)是\(f_i+sum_i\)最大的，\(j\)是\(f_j-sum_j\)最大的。那么由于\(sum_i>sum_j\)，所以其实\[f_i+sum_i+f_j-sum_j>f_i-sum_i+f_j+sum_j\]的。（哦，这里提一下，如果选择的\(i=j\)，那么尝试\(f_i+sum_i\)取次小值，或\(f_j-sum_j\)取次小值）所以我们只要保证\(f_i+sum_i+f_j-sum_j\)是最优的且\(i\not=j\)，一定可以保证\(i\)在\(j\)前面。

这里还有一个小细节，就是如何枚举下一个开始点时，要把上一个点\(i\)放到数组的末尾，还要解决\(sum_i\)变大的问题。其实只要把环上的点再重新加到原数组的末尾就好了，这样可以解决\(sum_i\)的问题。

四、代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define fi first#define se secondusing namespace std;typedef long long LL;typedef pair 
           
             PLI;typedef pair 
            
              PII;const int MAXN = 200000;const LL INF = 1e15;multiset 
             
               > set1;multiset 
              
                > set2;struct Edge { int to, nxt, w;} edge[MAXN + 5 << 1];LL ans, mxdis[MAXN + 5], sum[MAXN + 5 << 1], dia;int fir[MAXN + 5], ecnt, pre[MAXN + 5], eid[MAXN + 5], lpcnt, dfn[MAXN + 5], timer, n;PII lop[MAXN + 5 << 1];bool inl[MAXN + 5];template 
               
                 void read(T &x) { x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + c - 48; c = getchar(); } x *= f;}void addedge(int u, int v, int w) { edge[++ecnt].to = v; edge[ecnt].nxt = fir[u]; edge[ecnt].w = w; fir[u] = ecnt;}void getloop(int u) { dfn[u] = ++timer; for (int e = fir[u]; e && !lpcnt; e = edge[e].nxt) { int v = edge[e].to; if (v == pre[u]) continue; if (dfn[v]) { if (dfn[v] < dfn[u]) continue; for (int i = v; i != u; i = pre[i]) { lop[++lpcnt] = make_pair(i, edge[eid[i]].w); inl[i] = true; } lop[++lpcnt] = make_pair(u, edge[e].w); inl[u] = true; return; } pre[v] = u; eid[v] = e; getloop(v); }}void dfs(int u, int fa) { LL maxx = 0, minx = 0; mxdis[u] = 0; for (int e = fir[u]; e; e = edge[e].nxt) { int v = edge[e].to; if (v == fa || inl[v]) continue; dfs(v, u); mxdis[u] = max(mxdis[u], mxdis[v] + edge[e].w); if (mxdis[v] + edge[e].w > maxx) { minx = maxx; maxx = mxdis[v] + edge[e].w; } else if (mxdis[v] + edge[e].w > minx) minx = mxdis[v] + edge[e].w; } dia = max(dia, minx + maxx);}int main() { read(n); for (int i = 1; i <= n; ++i) { int u, v, w; read(u), read(v), read(w); addedge(u, v, w); addedge(v, u, w); } getloop(1); for (int i = 1; i <= lpcnt; ++i) { lop[i + lpcnt] = lop[i]; dfs(lop[i].fi, 0); } for (int i = 2; i <= lpcnt << 1; ++i) sum[i] = sum[i - 1] + lop[i - 1].se; for (int i = 1; i <= lpcnt; ++i) { set1.insert(make_pair(mxdis[lop[i].fi] + sum[i], i)); set2.insert(make_pair(mxdis[lop[i].fi] - sum[i], i)); } ans = INF; for (int i = 1; i <= lpcnt; ++i) { LL diameter; if (set1.begin()->se == set2.begin()->se) { multiset 
                
                  >::iterator ptr = set2.begin(); ++ptr; diameter = set1.begin()->first + ptr->first; ptr = set1.begin(); ++ptr; diameter = max(diameter, ptr->first + set2.begin()->first); } else diameter = set1.begin()->first + set2.begin()->first; ans = min(ans, diameter); set1.erase(make_pair(mxdis[lop[i].fi] + sum[i], i)); set2.erase(make_pair(mxdis[lop[i].fi] - sum[i], i)); set1.insert(make_pair(mxdis[lop[i + lpcnt].fi] + sum[i + lpcnt], i + lpcnt)); set2.insert(make_pair(mxdis[lop[i + lpcnt].fi] - sum[i + lpcnt], i + lpcnt)); } printf("%lld\n", max(ans, dia)); return 0;}
                
               
              
             
            
           
          
         
        
       
      
     
    

• TIPS
  1. 前面提到树的直径是不变的，所以最后的答案不应该超过每个环上的点对应的树的直径。
  2. 数组别忘了开两倍...