目录
BZOJ1509 逃学的小孩题解ｃｏｄｅ
BZOJ1509 逃学的小孩
题目传送门
题解
比较简单的一道题目，首先由于要构造一个最坏的情况，所以一定会走\(A\)到\(B\)这条路，那么\(A\)和\(B\)的地点一定是在树直径的两个端点上的。所以我们找出直径的两个端点之后，处理每个点到两个直径端点的距离\(d1[i]\)和\(d2[i]\)，然后每个点对答案的贡献就是\(min(d1[i],d2[i])\)，只需要找出这个的最大值就行了，再加上直径的长度就是答案了。
ｃｏｄｅ
#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上百实例源码以及开源项目
