?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
109862719 |
Practice: luogu_bot3 |
835F - 34 | GNU C++11 | Accepted | 296 ms | 139400 KB | 2021-03-13 13:03:47 | 2021-03-13 13:03:47 |
#include<bits/stdc++.h> #define int long long #define _to e[i].to const int N=500050,inf=998244353353353; using namespace std; struct edge{int to,nx,w;}e[N<<2]; int hd[N],S; map<int,int> a[N]; void add(int fr,int to,int w){ e[++S]=(edge){to,hd[fr],w},hd[fr]=S; } int w[N],n,x,y,z,stk[N],tp,v[N],cnt,s[N],fl,ic[N],d[N],ans,l[N],r[N],l0[N],r0[N],res,ans2=inf; void fcr(int k,int fa){ stk[++tp]=k,v[k]=1; for(int i=hd[k];i;i=e[i].nx) if(_to!=fa) if(v[_to]){ if(!fl&&(fl=1)){ while(stk[tp]!=_to) ic[s[++cnt]=stk[tp--]]=1; ic[s[++cnt]=stk[tp--]]=1; } }else fcr(_to,k); --tp; } void dfs(int k,int fa){ int mx=0,sc=0; for(int i=hd[k];i;i=e[i].nx) if(_to!=fa&&!ic[_to]){ dfs(_to,k),d[k]=max(d[k],d[_to]+e[i].w); if(d[_to]+e[i].w>=mx)sc=mx,mx=d[_to]+e[i].w; else sc=max(sc,d[_to]+e[i].w); } ans=max(ans,sc+mx); } main(){ scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&x,&y,&z),add(x,y,z),add(y,x,z),a[x][y]=a[y][x]=z; fcr(1,0); for(int i=1;i<=cnt;i++)dfs(s[i],0),w[i]=w[i-1]+a[s[i-1==0?cnt:i-1]][s[i]]; res=l[0]=l0[0]=-inf; for(int i=1;i<=cnt;i++) l0[i]=max(l0[i-1],d[s[i]]+w[i]+res),l[i]=max(l[i-1],d[s[i]]+w[i]),res=max(res,d[s[i]]-w[i]); res=r[cnt+1]=r0[cnt+1]=-inf; for(int i=cnt;i;i--) r0[i]=max(r0[i+1],d[s[i]]-w[i]+res),r[i]=max(r[i+1],d[s[i]]+w[cnt]-w[i]),res=max(res,d[s[i]]+w[i]); for(int i=1;i<=cnt;i++) ans2=min(ans2,max(l[i-1]+r[i],max(l0[i-1],r0[i]))); printf("%lld",max(ans,ans2)); }
?
?
?
?