算法：基环树DP
这道题是我学完基环树后自己做出来的第一道题目hh，虽然调了很久 和这道题目有些类似的题目有IOI2008 Island 这题
https://www.luogu.com.cn/problem/P4381
下面来说这一题的思路：
n点n边，任意两点之间都有一条双向边，因此这是一颗基环树，对于基环树DP的题目，我们首先做的应该是找到环并断开
- 1.找环
void dfs_s(int u,int fa){
st[u] = ins[u] = true;
for(int i=h[u];~i;i=ne[i]){
//if(i == (from^1)) continue; //用边判重会导致有三个点RE
int j = e[i];
if(j==fa) continue;
fu[j] = u,fw[j] = w[i];
if(!st[j]) dfs_s(j,u);
else if(ins[j]){
//debug(u);debug(j);
brk = w[i];
LL sum = 0;
for(int k = u;k!=j;k=fu[k]){
s[k] = sum;
sum += fw[k];
cir[++ed] = k;
}
s[j] = sum, cir[++ed] = j;
}
}
ins[u] = false;
}
找环有一个技巧在dfs的时候存储每个结点的访问状态，然后当遇到一个结点已经被访问过了，说明找到了环。然后同时根据记录的反向边而新开的数组fu[]就可以找出完整的环了
！注意在判断是否重复走一个点的时候不能用边判重，需要用是否为父节点来判重,不然可能只有70pts
这个时候我们断环成链，需要依次计算出在链上每一条边断开的形成的最长直径，在所有的直径中取最小的。之所以要取最小的是因为我们依次断开的那条边也是可以走的，但是在我们断开他之后不一定会被算到；
因此需要预处理四个数组来协助我们在O(n)的复杂度内完成最长直径的寻找
- 处理数组找直径
//处理出后缀和和A[]数组,起点出发到i点子树或者左边子树的最大值
for(int j=1;j<=sz-1;j++){
sub[j] = sum[sz] - sum[j];
if(j==1) A[j] = d[j];
else A[j] = max(A[j-1] , d[j] + sum[j]);
//debug(j);debug(A[j]);
}
//处理B[]数组
for(int j=sz-1;j>=1;j--){
if(j==sz-1) B[j] = d[j+1];
else B[j] = max(B[j+1],d[j+1] + sub[j+1]);
//debug(sub[j]);
}
mn=-0x3f3f3f3f;
//处理C[]数组
for(int j=1;j<=sz-1;j++){
if(j==1) C[j] = max(d[j],tr[j]);
else C[j] = max({C[j-1],tr[j],d[j]+sum[j]+mn});
mn = max(mn,d[j]-sum[j]);
}
mn=-0x3f3f3f3f;
//处理D[]数组
for(int j=sz-1;j>=1;j--){
if(j==sz-1) D[j] = max(tr[j+1],d[j+1]);
else D[j] = max({D[j+1],tr[j+1],d[j+1]+sub[j+1]+mn});
mn = max(mn,d[j+1]-sub[j+1]);
}
//debug(brk);
for(int i=1;i<=sz-1;i++){
//debug(A[i]);debug(B[i]);debug(C[i]);debug(D[i]);debug(A[i]+B[i]+brk);debug(ans);
ans=min(ans,max({A[i],B[i],C[i],D[i],A[i]+B[i]+brk}));
}
下面是完整的代码：
#include<bits/stdc++.h>
using namespace std;
//================================
#define debug(a) cout << #a": " << a << endl;
#define rep(i, ll,rr) for(int i = ll; i <= rr; ++i)
const int N =1e5+10,INF = 1e9;
//================================
typedef pair<int,int> pii;
#define x first
#define y second
typedef long long LL; typedef unsigned long long ULL; typedef long double LD;
inline LL read() { LL s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(LL x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; LL tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
//=================================
int n,m,a,b;
LL e[N*2],ne[N*2],h[N],idx=0,fu[N*2],tr[N*2],brk; //tr[]维护当前树上的直径
LL w[N*2],fw[N],d[N*2],s[N*2],sum[N*2],c;
LL A[N],B[N],C[N],D[N],sub[N],mn=-0x3f3f3f3f;//mn维护d[x]-s[x]的最大值
int cir[N],ed=0,q[N*2];
bool st[N*2],ins[N*2];
LL res,ans=1e18;
/*
sum为前缀和
1.A[]:环上第一个点出发到i点的子树或者左边子树的最大距离 d[i] + sum[i]
2.B[]:环上最后一个点出发到i或者右边子树的最大距离 d[i] + sub[i]
3.C[]:i之前的直径 d[x] + d[y] - sum[x] + sum[y]
4.D[]:i之后的直径 d[x] + d[y] + sum[x] - sum[y]
*/
void add(int a,int b,LL c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs_s(int u,int fa){
st[u] = ins[u] = true;
for(int i=h[u];~i;i=ne[i]){
//if(i == (from^1)) continue; //用边判重会导致有三个点RE
int j = e[i];
if(j==fa) continue;
fu[j] = u,fw[j] = w[i];
if(!st[j]) dfs_s(j,u);
else if(ins[j]){
//debug(u);debug(j);
brk = w[i];
LL sum = 0;
for(int k = u;k!=j;k=fu[k]){
s[k] = sum;
sum += fw[k];
cir[++ed] = k;
}
s[j] = sum, cir[++ed] = j;
}
}
ins[u] = false;
}
LL dfs_d(int u,int id){
st[u] = true;
LL d1 = 0 , d2 = 0 ;
for(int i=h[u];~i;i=ne[i]){
int j = e[i];
if(st[j]) continue;
LL length = dfs_d(j,id)+w[i];
if(length > d1) d2 = d1,d1 = length;
else if(length > d2) d2 = length;
}
tr[id] = d1 + d2;
return d1;
}
signed main(){
memset(h,-1,sizeof h);
n=read();
rep(i,1,n){
a=read(),b=read(),c=read();
add(a,b,c),add(b,a,c);
}
for(int i=1;i<=n;i++)
if(!st[i])
dfs_s(i,-1);
memset(st,0,sizeof st);
for(int i=1;i<=ed;i++) st[cir[i]] = true; //将圆上的点全部标记一下，防止被找过
// ans = 0.0;
int sz = 1;
for(int j = 1;j <= ed; j++){
int k = cir[j];
d[sz] = dfs_d(k,sz);
sum[sz] = s[k];
sz ++ ;
}sz--;
//debug(sz);debug(sum[sz]);
//处理出后缀和和A[]数组,起点出发到i点子树或者左边子树的最大值
for(int j=1;j<=sz-1;j++){
sub[j] = sum[sz] - sum[j];
if(j==1) A[j] = d[j];
else A[j] = max(A[j-1] , d[j] + sum[j]);
//debug(j);debug(A[j]);
}
//处理B[]数组
for(int j=sz-1;j>=1;j--){
if(j==sz-1) B[j] = d[j+1];
else B[j] = max(B[j+1],d[j+1] + sub[j+1]);
//debug(sub[j]);
}
mn=-0x3f3f3f3f;
//处理C[]数组
for(int j=1;j<=sz-1;j++){
if(j==1) C[j] = max(d[j],tr[j]);
else C[j] = max({C[j-1],tr[j],d[j]+sum[j]+mn});
mn = max(mn,d[j]-sum[j]);
}
mn=-0x3f3f3f3f;
//处理D[]数组
for(int j=sz-1;j>=1;j--){
if(j==sz-1) D[j] = max(tr[j+1],d[j+1]);
else D[j] = max({D[j+1],tr[j+1],d[j+1]+sub[j+1]+mn});
mn = max(mn,d[j+1]-sub[j+1]);
}
//debug(brk);
for(int i=1;i<=sz-1;i++){
//debug(A[i]);debug(B[i]);debug(C[i]);debug(D[i]);debug(A[i]+B[i]+brk);debug(ans);
ans=min(ans,max({A[i],B[i],C[i],D[i],A[i]+B[i]+brk}));
}
ans & 1 ? printf("%lld.5",ans/2) : printf("%lld.0",ans/2);
return 0;
}
京公网安备 11010502036488号