?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
103154931 |
Practice: luogu_bot5 |
835F - 34 | GNU C++11 | Accepted | 187 ms | 35984 KB | 2021-01-04 11:35:31 | 2021-01-04 11:35:31 |
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+77,inf=1e18+5; struct E { int to,w,next; }e[N<<1]; int n,cnt=0,tot=0,ans1=0,ans2=inf,yjy,ls[N],C[N],vis[N],f[N]; int W[N],l[N],lans[N],r[N],rans[N]; void add(int u,int v,int w) { e[++tot].to=v; e[tot].next=ls[u]; ls[u]=tot; e[tot].w=w; } int pre(int x,int fa=-1) { if(vis[x]) return x;else vis[x]=-1; for(int i=ls[x]; i; i=e[i].next) { int v=e[i].to; if(v==fa) continue; yjy=pre(v,x); if(yjy) return C[++cnt]=x,W[cnt]=e[i].w,vis[x]=1,yjy==x?0:yjy; } return 0; } void dfs(int x,int fa=-1) { for(int i=ls[x]; i; i=e[i].next) { int v=e[i].to; if(vis[v]==1||v==fa) continue; dfs(v,x); ans1=max(ans1,f[x]+f[v]+e[i].w),f[x]=max(f[x],f[v]+e[i].w); } } signed main() { scanf("%lld",&n); for(int i=1,x,y,w; i<=n; i++) scanf("%lld%lld%lld",&x,&y,&w),add(x,y,w),add(y,x,w); pre(1),W[0]=0; for(int i=1; i<=cnt; i++) dfs(C[i]),W[i]+=W[i-1]; yjy=l[0]=lans[0]=-inf; for(int i=1; i<=cnt; i++) lans[i]=max(lans[i-1],f[C[i]]+W[i]+yjy), l[i]=max(l[i-1],f[C[i]]+W[i]), yjy=max(yjy,f[C[i]]-W[i]); yjy=r[cnt+1]=rans[cnt+1]=-inf; for(int i=cnt; i>=1; i--) rans[i]=max(rans[i+1],f[C[i]]-W[i]+yjy), r[i]=max(r[i+1],f[C[i]]+W[cnt]-W[i]), yjy=max(yjy,f[C[i]]+W[i]); for(int i=1; i<=cnt; i++) ans2=min(ans2,max(l[i-1]+r[i],max(lans[i-1],rans[i]))); printf("%lld\n",max(ans1,ans2)); }
?
?
?
?