?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
97181172 |
Practice: jiangshanxyz |
835F - 34 | GNU C++11 | Accepted | 140 ms | 50068 KB | 2020-10-30 17:47:38 | 2020-10-30 17:47:38 |
#include<bits/stdc++.h> #define int long long using namespace std; int n,x,y,z,t,ts,s1,s2,res; int head[400010],b[400010],c[400010],w[400010],f[400010],l[400010],ll[400010],r[400010],rr[400010]; struct edge { int to,w,next; }e[400010]; void add(int x,int y,int z) { t++; e[t].to=y; e[t].w=z; e[t].next=head[x]; head[x]=t; } int find(int x,int f=-1) { if(b[x])return x; else b[x]=-1; for(int i=head[x];i>0;i=e[i].next) if(e[i].to!=f) { res=find(e[i].to,x); if(res) { c[++ts]=x; w[ts]=e[i].w; b[x]=1; if(res==x)return 0; else return res; } } return 0; } void dfs(int x,int fa=-1) { for(int i=head[x];i;i=e[i].next) if(b[e[i].to]!=1&&e[i].to!=fa) { dfs(e[i].to,x); s1=max(s1,f[x]+f[e[i].to]+e[i].w); f[x]=max(f[x],f[e[i].to]+e[i].w); } } signed main() { cin>>n; for(int i=1;i<=n;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } find(1); w[0]=0; for(int i=1;i<=ts;i++)dfs(c[i]),w[i]+=w[i-1]; res=l[0]=ll[0]=-2e18; for(int i=1;i<=ts;i++) { ll[i]=max(ll[i-1],f[c[i]]+w[i]+res); l[i]=max(l[i-1],f[c[i]]+w[i]); res=max(res,f[c[i]]-w[i]); } res=r[ts+1]=rr[ts+1]=-2e18; for(int i=ts;i>=1;i--) { rr[i]=max(rr[i+1],f[c[i]]-w[i]+res); r[i]=max(r[i+1],f[c[i]]+w[ts]-w[i]); res=max(res,f[c[i]]+w[i]); } s2=2e18; for(int i=1;i<=ts;i++)s2=min(s2,max(l[i-1]+r[i],max(ll[i-1],rr[i]))); cout<<max(s1,s2); return 0; }
?
?
?
?