?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
87816279 |
Practice: luogu_bot4 |
835F - 34 | GNU C++11 | Accepted | 155 ms | 39768 KB | 2020-07-24 03:22:19 | 2020-07-24 03:22:19 |
#include <bits/stdc++.h> #define int long long #define ri register int #define N 200005 using namespace std; const int inf=1e18; int n,cnt=0,tot=0,ans1=0,ans2=inf,h[N],d[N],v[N],w[N],l1[N],l2[N],r1[N],r2[N],cir[N]; struct edge { int u,v,w; } e[N<<1]; inline void add(int u,int v,int w) { e[++tot]=(edge) {h[u],v,w},h[u]=tot; } int dfs1(int x,int f) { if (v[x]) return x; v[x]=-1; for (ri i=h[x]; i; i=e[i].u) if (e[i].v^f) { int t=dfs1(e[i].v,x); if (t) { cir[++cnt]=x,w[cnt]=e[i].w,v[x]=1; if (t^x) return t; return 0; } } return 0; } void dfs2(int x,int f) { for (ri i=h[x]; i; i=e[i].u) if (v[e[i].v]^1&&e[i].v^f) dfs2(e[i].v,x),ans1=max(ans1,d[x]+d[e[i].v]+e[i].w),d[x]=max(d[x],d[e[i].v]+e[i].w); } signed main() { scanf("%lld",&n); for (ri i=1,x,y,z; i<=n; i++) scanf("%lld%lld%lld",&x,&y,&z),add(x,y,z),add(y,x,z); dfs1(1,0),l1[0]=l2[0]=r1[cnt+1]=r2[cnt+1]=-inf; for (ri i=1; i<=cnt; i++) dfs2(cir[i],0),w[i]+=w[i-1]; for (ri i=1,tmp=-inf; i<=cnt; i++) l1[i]=max(l1[i-1],d[cir[i]]+w[i]+tmp),l2[i]=max(l2[i-1],d[cir[i]]+w[i]),tmp=max(tmp,d[cir[i]]-w[i]); for (ri i=cnt,tmp=-inf; i; i--) r1[i]=max(r1[i+1],d[cir[i]]-w[i]+tmp),r2[i]=max(r2[i+1],d[cir[i]]-w[i]+w[cnt]),tmp=max(tmp,d[cir[i]]+w[i]); for (ri i=1; i<=cnt; i++) ans2=min(ans2,max(max(l1[i-1],r1[i]),l2[i-1]+r2[i])); printf("%lld",max(ans1,ans2)); return 0; }
?
?
?
?