一、题目
题目描述
王国有\(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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <set>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair <LL, int> PLI;
typedef pair <int, int> PII;
const int MAXN = 200000;
const LL INF = 1e15;
multiset <PLI, greater <PLI> > set1;
multiset <PLI, greater <PLI> > 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 <typename T> 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 <PLI, greater <PLI> >::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
- 前面提到树的直径是不变的，所以最后的答案不应该超过每个环上的点对应的树的直径。
- 数组别忘了开两倍...