|

General

# Author Problem Lang Verdict Time Memory Sent Judged
87750686 Practice:
luogu_bot4
835F - 34 GNU C++11 Accepted 140 ms 32276 KB 2020-07-23 11:46:27 2020-07-23 11:46:27

→ Source
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005,INF=1e18+5;
struct edge{
int to,wei,nxt;
}e[N<<1];
inline void adde(int x,int y,int w) {
}
inline int fnd(int x,int fa=-1) {
if(vis[x]) return x;
else vis[x]=-1;
if(e[i].to!=fa) {
res=fnd(e[i].to,x);
if(res) {
cir[++cnt]=x;
we[cnt]=e[i].wei;
vis[x]=1;
if(res==x) return 0;
return res;
}
}
}
return 0;
}
inline void dfs(int x,int fa=-1) {
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() {
scanf("%lld",&n);
for(int i=1,x,y,w;i<=n;i++) {
scanf("%lld%lld%lld",&x,&y,&w);
}
fnd(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])));
}
printf("%lld\n",max(ans1,ans2));
return 0;
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?