题意
给定(n)个点(n)条边的连通图，要求删去一条边，使得剩下的图仍是一个连通图，并且图中距离最远的两个点的距离最小
解法
(n)个点(n)条边的连通图即为基环树
要删去一条边使得剩下的图仍是连通图，我们删除的一定是环上的边，剩下的图一定是一颗树
那么树上距离最远的两个点的距离就是树的直径
暴力枚举环上断边求直径是(O(N^2))的，考虑优化
单独考虑环上的点，把环上的点编号为(1)至(m)
断边后的直径有两种情况：
-
直径不经过环( ightarrow) 答案即为所有基环外向树中的直径
-
直径经过环 ( ightarrow) 此时又要分两种情况进行考虑
-
使用了(1 o m)这条边
预处理出倒(L)形路径的前缀后缀最大值
-
未使用(1 o m)这条边
直径一定是从某个子树的最深处出发，在环上遍历了某些点，再回到某个子树中去的
预处理出(Pi)形路径的前缀后缀最大值
-
有很多细节，巨难打。。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int read();
int n;
int cap;
int head[N], to[N], nxt[N], val[N];
int deg[N];
long long ans;
inline void add(int x, int y, int z) {
to[++cap] = y, nxt[cap] = head[x], head[x] = cap, val[cap] = z;
}
int p;
int cir[N], mrk[N], book[N];
long long DIS, len[N];
void Dfs_cir(int x) {
book[x] = mrk[x] = 1, cir[++p] = x;
for (int i = head[x]; i; i = nxt[i]) {
if (!mrk[to[i]]) {
Dfs_cir(to[i]);
break;
}
}
}
long long f[N][5];
void Dfs_diametre(int x, int fa) {
for (int i = head[x]; i; i = nxt[i]) {
if (to[i] == fa || book[to[i]]) continue;
Dfs_diametre(to[i], x);
if (f[to[i]][1] + val[i] >= f[x][1])
f[x][2] = f[x][1], f[x][1] = f[to[i]][1] + val[i];
else
f[x][2] = max(f[x][2], f[to[i]][1] + val[i]);
}
}
int top;
int stk[N];
void Get_cir() {
for (int i = 1; i <= n; ++i)
if (deg[i] == 1)
stk[++top] = i;
while (top) {
int u = stk[top--];
mrk[u] = 1;
for (int i = head[u]; i; i = nxt[i]) {
deg[u]--, deg[to[i]]--;
if (deg[to[i]] == 1)
stk[++top] = to[i];
}
}
for (int i = 1; i <= n; ++i)
if (!mrk[i]) Dfs_cir(i);
}
void Get_diametre() {
for (int i = 1; i <= p; ++i) {
Dfs_diametre(cir[i], 0);
ans = max(ans, f[cir[i]][1] + f[cir[i]][2]);
}
}
long long pre[N], suf[N];
long long f1[N], f2[N], g1[N], g2[N];
void prepare_for_ans() {
for (int i = 1; i < p; ++i)
for (int j = head[cir[i]]; j; j = nxt[j])
if (to[j] == cir[i + 1])
len[i] = val[j];
for (int i = head[cir[p]]; i; i = nxt[i])
if (to[i] == cir[1]) {
DIS = val[i];
break;
}
for (int i = 1; i < p; ++i) pre[i] = pre[i - 1] + len[i];
for (int i = p - 1; i >= 1; --i) suf[i] = suf[i + 1] + len[i];
for (int i = 1; i <= p; ++i) f1[i] = max(f1[i - 1], pre[i - 1] + f[cir[i]][1]);
for (int i = p; i >= 1; --i) f2[i] = max(f2[i + 1], suf[i] + f[cir[i]][1]);
long long now = f[cir[1]][1];
for (int i = 2; i <= p; ++i) {
now += len[i - 1];
g1[i] = max(g1[i - 1], now + f[cir[i]][1]);
now = max(now, f[cir[i]][1]);
}
now = f[cir[p]][1];
for (int i = p - 1; i >= 1; --i) {
now += len[i];
g2[i] = max(g2[i + 1], now + f[cir[i]][1]);
now = max(now, f[cir[i]][1]);
}
}
void Get_ans() {
prepare_for_ans();
long long res = g2[1];
for (int i = 1; i < p; ++i)
res = min(res, max(max(g1[i], g2[i + 1]), f1[i] + f2[i + 1] + DIS));
ans = max(ans, res);
}
int main() {
n = read();
for (int i = 1; i <= n; ++i) {
int u = read(), v = read(), w = read();
add(u, v, w), add(v, u, w);
deg[u]++, deg[v]++;
}
Get_cir();
Get_diametre();
Get_ans();
printf("%lld
", ans);
return 0;
}
#define gc getchar
int read() {
int x = 0, c = gc();
while (c < '0' || c > '9') c = gc();
while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = gc();
return x;
}