算法1
首先显然两家人在直径端点上,然后只要枚举求出其它点到两个端点的距离的较小值的最大值即可,LCA实现。
C++ 代码
#include <bits/stdc++.h>
#define For(i, a, b) for(register int i = (a); i <= (b); ++i)
#define Rof(i, a, b) for(register int i = (a); i >= (b); --i)
#define INF 0x3f3f3f3f
#define LL long long
#define MaxN 200010
#define mp(a, b) make_pair(a, b)
#define fi first
#define se second
using namespace std;
typedef pair<int, LL> PII;
int N, M, Head[MaxN], Cnt = 1, u, v, w, Dot1, Dot2, F[21][MaxN], Depth[MaxN];
LL Dec, Ans1, Ans2, W[21][MaxN];
struct Xjh {int Ver, Next, Weight;} E[MaxN << 1];
void Add_Edge(int u, int v, int w) {E[++Cnt].Ver = v, E[Cnt].Weight = w, E[Cnt].Next = Head[u], Head[u] = Cnt;}
bool Vis[MaxN];
int BFS(int S) {
int Ret = S; LL Pos = 0; memset(Vis, 0, sizeof(Vis));
queue<PII> Q; Q.push(mp(S, 0)); Vis[S] = 1;
while(!Q.empty()) {
PII Now = Q.front(); Q.pop();
if(Now.se > Pos) Pos = Now.se, Ret = Now.fi;
for(int i = Head[Now.fi], v; i; i = E[i].Next) {
if(Vis[v = E[i].Ver]) continue; Vis[v] = 1;
Q.push(mp(v, 1ll * Now.se + E[i].Weight));
}
}
Dec = Pos;
return Ret;
}
void Dfs(int u, int f) {
F[0][u] = f; Depth[u] = Depth[f] + 1;
for(int i = Head[u], v; i; i = E[i].Next) {
if((v = E[i].Ver) == f) continue;
Dfs(v, u); W[0][v] = E[i].Weight;
}
}
void Init() {
For(k, 1, 18) For(i, 1, N) {
F[k][i] = F[k - 1][F[k - 1][i]];
W[k][i] = W[k - 1][i] + W[k - 1][F[k - 1][i]];
}
}
LL Dis(int x, int y) {
LL Ret = 0;
if(Depth[x] < Depth[y]) swap(x, y);
Rof(k, 18, 0) if(Depth[F[k][x]] >= Depth[y]) Ret += W[k][x], x = F[k][x];
if(x == y) return Ret;
Rof(k, 18, 0) if(F[k][x] != F[k][y]) {
Ret += W[k][x] + W[k][y];
x = F[k][x], y = F[k][y];
}
return Ret + W[0][x] + W[0][y];
}
int main() {
scanf("%d%d", &N, &M); For(i, 1, M) scanf("%d%d%d", &u, &v, &w), Add_Edge(u, v, w), Add_Edge(v, u, w);
Dot1 = BFS(1), Dot2 = BFS(Dot1), Ans1 = Dec;
Dfs(1, 1); Init(); For(i, 1, N) Ans2 = max(Ans2, min(Dis(i, Dot1), Dis(i, Dot2)));
printf("%lld\n", Ans1 + Ans2);
return 0;
}
呃呃呃为什么我用的o(N)算法都会t掉
绝了,明明可以遍历一遍图求出两端与所有点的距离,还要LCA求,O(N)不香吗qaq