?
№ | Отправитель | Задача | Язык | Вердикт | Время | Память | Отослано | Протест. | |
---|---|---|---|---|---|---|---|---|---|
89297365 |
Дорешивание: luogu_bot2 |
835F - 34 | GNU C++11 | Полное решение | 124 мс | 33512 КБ | 2020-08-08 04:24:42 | 2020-08-08 04:24:42 |
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+5; const ll Inf=0x3f3f3f3f3f3f3f3f; int n,x,y,z,cnt,tot,head[maxn],vis[maxn]; ll res,r[maxn],l[maxn],l0[maxn],r0[maxn],sum[maxn],ans1,ans2=Inf,f[maxn],cir[maxn]; struct Edge{ int to,next,w; }e[maxn<<1]; void add(int u,int v,int w) { e[++cnt].to=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt; } int fnd(int u,int fa=-1) { if(vis[u]) return u; vis[u]=-1; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v!=fa) { res=fnd(v,u); if(res) return cir[++tot]=u,sum[tot]=e[i].w,vis[u]=1,res==u?0:res; } } return 0; } void dfs(int u,int fa=-1) { for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(vis[v]!=1&&v!=fa) { dfs(v,u); ans1=max(ans1,f[u]+f[v]+e[i].w); f[u]=max(f[u],f[v]+e[i].w); } } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } fnd(1); sum[0]=0; for(int i=1;i<=tot;i++) { dfs(cir[i]); sum[i]+=sum[i-1]; } res=l[0]=l0[0]=-Inf; for(int i=1;i<=tot;i++) { l0[i]=max(l0[i-1],f[cir[i]]+sum[i]+res); l[i]=max(l[i-1],f[cir[i]]+sum[i]); res=max(res,f[cir[i]]-sum[i]); } res=r[tot+1],r0[tot+1]=-Inf; for(int i=tot;i>=1;i--) { r0[i]=max(r0[i+1],f[cir[i]]-sum[i]+res); r[i]=max(r[i+1],f[cir[i]]+sum[tot]-sum[i]); res=max(res,f[cir[i]]+sum[i]); } for(int i=1;i<=tot;i++) { ans2=min(ans2,max(l[i-1]+r[i],max(l0[i-1],r0[i]))); } printf("%lld\n",max(ans1,ans2)); return 0; }
?
?
?
?