BZOJ1509 逃学的小孩

mac2022-06-30  145

目录

BZOJ1509 逃学的小孩题解code

BZOJ1509 逃学的小孩

题目传送门

题解

比较简单的一道题目,首先由于要构造一个最坏的情况,所以一定会走\(A\)\(B\)这条路,那么\(A\)\(B\)的地点一定是在树直径的两个端点上的。所以我们找出直径的两个端点之后,处理每个点到两个直径端点的距离\(d1[i]\)\(d2[i]\),然后每个点对答案的贡献就是\(min(d1[i],d2[i])\),只需要找出这个的最大值就行了,再加上直径的长度就是答案了。

code

#include <bits/stdc++.h> using namespace std; typedef long long ll; bool Finish_read; template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;} template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');} template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');} template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);} /*================Header Template==============*/ #define PAUSE printf("Press Enter key to continue..."); fgetc(stdin); const int maxn=2e5+500; int n,m,tot,st1,st2; ll mxdis; struct edge { int to,nxt; ll w; }E[maxn<<2]; int head[maxn],p[maxn][20],dep[maxn]; ll d1[maxn],d2[maxn]; /*==================Define Area================*/ void addedge(int u,int v,ll w) { E[++tot].to=v;E[tot].nxt=head[u];head[u]=tot;E[tot].w=w; E[++tot].to=u;E[tot].nxt=head[v];head[v]=tot;E[tot].w=w; } void dfs1(int o,int fa,ll dis) { if(dis>mxdis) { mxdis=dis; st1=o; } for(int i=head[o];~i;i=E[i].nxt) { int to=E[i].to; if(to==fa) continue ; dfs1(to,o,dis+E[i].w); } } void dfs2(int o,int fa,ll dis) { if(dis>mxdis) { mxdis=dis; st2=o; } for(int i=head[o];~i;i=E[i].nxt) { int to=E[i].to; if(to==fa) continue ; dfs2(to,o,dis+E[i].w); } } void Getdis1(int o,int fa,ll dis) { d1[o]=dis; for(int i=head[o];~i;i=E[i].nxt) { int to=E[i].to; if(to==fa) continue ; Getdis1(to,o,dis+E[i].w); } } void Getdis2(int o,int fa,ll dis) { d2[o]=dis; for(int i=head[o];~i;i=E[i].nxt) { int to=E[i].to; if(to==fa) continue ; Getdis2(to,o,dis+E[i].w); } } int main() { memset(head,-1,sizeof head); read(n);read(m); ll w; for(int i=1,u,v;i<=m;i++) { read(u);read(v);read(w); addedge(u,v,w); } mxdis=0; dfs1(1,0,0); mxdis=0; dfs2(st1,0,0); Getdis1(st1,0,0); Getdis2(st2,0,0); ll ans=0; for(int i=1;i<=n;i++) { ll ret=min(d1[i],d2[i]); ans=max(ret,ans); } printf("%lld\n",ans+mxdis); return 0; } /* 4 3 1 2 1 2 3 1 3 4 1 */

转载于:https://www.cnblogs.com/Apocrypha/p/9435246.html

相关资源:JAVA上百实例源码以及开源项目
最新回复(0)