?
№ | Отправитель | Задача | Язык | Вердикт | Время | Память | Отослано | Протест. | |
---|---|---|---|---|---|---|---|---|---|
98568506 |
Дорешивание: jiangshanxyz |
835F - 34 | GNU C++11 | Полное решение | 124 мс | 50068 КБ | 2020-11-16 16:31:46 | 2020-11-16 16:31:46 |
#include<bits/stdc++.h> #define Max 2e18 #define Maxn 400010 #define int long long using namespace std; int n,x,y,z,t,ts,sum1,sum2,res; int h[Maxn],b[Maxn],c[Maxn],w[Maxn],f[Maxn],l1[Maxn],l2[Maxn],r1[Maxn],r2[Maxn]; struct edge { int to,w,next; }e[Maxn]; void add(int x,int y,int z) { t++; e[t].to=y; e[t].w=z; e[t].next=h[x]; h[x]=t; } int find(int x,int f=-1) { if(b[x])return x; else b[x]=-1; for(int i=h[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=h[x];i;i=e[i].next) if(b[e[i].to]!=1&&e[i].to!=fa) { dfs(e[i].to,x); sum1=max(sum1,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=l1[0]=l2[0]=-Max; for(int i=1;i<=ts;i++) { l2[i]=max(l2[i-1],f[c[i]]+w[i]+res); l1[i]=max(l1[i-1],f[c[i]]+w[i]); res=max(res,f[c[i]]-w[i]); } res=r1[ts+1]=r2[ts+1]=-Max; for(int i=ts;i>=1;i--) { r2[i]=max(r2[i+1],f[c[i]]-w[i]+res); r1[i]=max(r1[i+1],f[c[i]]+w[ts]-w[i]); res=max(res,f[c[i]]+w[i]); } sum2=Max; for(int i=1;i<=ts;i++)sum2=min(sum2,max(l1[i-1]+r1[i],max(l2[i-1],r2[i]))); cout<<max(sum1,sum2); return 0; }
?
?
?
?