?
№ | Отправитель | Задача | Язык | Вердикт | Время | Память | Отослано | Протест. | |
---|---|---|---|---|---|---|---|---|---|
108320903 |
Дорешивание: luogu_bot1 |
835F - 34 | GNU C++11 | Полное решение | 1170 мс | 35968 КБ | 2021-02-23 19:09:21 | 2021-02-23 19:09:21 |
#include<bits/stdc++.h> #define int long long using namespace std; const int N=200005,INF=1e18+5; struct edge{ int to; int wei; int nxt; }e[N*2]; int n,tot=0,cnt=0,ans1=0,ans2=INF,res,head[N],cir[N],vis[N],f[N],we[N],l[N],l0[N],r[N],r0[N]; void add(int x,int y,int w){ e[++tot]=(edge){y,w,head[x]}; head[x]=tot; } int get_cir(int x,int fa=-1){ if(vis[x]){ return x; } else{ vis[x]=-1; } for(int i=head[x];i;i=e[i].nxt){ if(e[i].to!=fa){ res=get_cir(e[i].to,x); if(res){ return cir[++cnt]=x,we[cnt]=e[i].wei,vis[x]=1,res==x?0:res; } } } return 0; } void dfs(int x,int fa=-1){ for(int i=head[x];i;i=e[i].nxt) if(vis[e[i].to]!=1&&e[i].to!=fa) dfs(e[i].to,x),ans1=max(ans1,f[x]+f[e[i].to]+e[i].wei),f[x]=max(f[x],f[e[i].to]+e[i].wei); } signed main(){ cin>>n; memset(vis,0,sizeof(vis)); memset(f,0,sizeof(f)); for(int i=1;i<=n;i++){ int x,y,z; cin>>x>>y>>z; add(x,y,z); add(y,x,z); } get_cir(1); we[0]=0; for(int i=1;i<=cnt;i++){ dfs(cir[i]); we[i]+=we[i-1]; } res=l[0]=l0[0]=-INF; for(int i=1;i<=cnt;i++){ l0[i]=max(l0[i-1],f[cir[i]]+we[i]+res); l[i]=max(l[i-1],f[cir[i]]+we[i]); res=max(res,f[cir[i]]-we[i]); } res=r[cnt+1]=r0[cnt+1]=-INF; for(int i=cnt;i>=1;i--){ r0[i]=max(r0[i+1],f[cir[i]]-we[i]+res); r[i]=max(r[i+1],f[cir[i]]+we[cnt]-we[i]); res=max(res,f[cir[i]]+we[i]); } for(int i=1;i<=cnt;i++){ ans2=min(ans2,max(l[i-1]+r[i],max(l0[i-1],r0[i]))); } cout<<max(ans1,ans2)<<endl; return 0; }
?
?
?
?