BZOJ 1509: [NOI2003]逃学的小孩

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1509

直接求出树的直径,枚举每个点更新一遍答案。

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#define maxn 200500
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define eps 1e-8
#define ll long long
#define mm 999911659
using namespace std;
struct data{int obj,pre; ll c;
}e[maxn*];
int head[maxn],tot,s,t,n,m;
ll dis[maxn],dis2[maxn],dis3[maxn],ans;
ll read(){
ll x=,f=; char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-; ch=getchar();}
while (isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
void insert(int x,int y,ll z){
e[++tot].obj=y; e[tot].pre=head[x]; e[tot].c=z; head[x]=tot;
}
void dfs(int u,int fa){
for (int j=head[u];j;j=e[j].pre){
int v=e[j].obj;
if (v!=fa){
dis[v]=dis[u]+e[j].c;
if (dis[v]>dis[s]) s=v;
dfs(v,u);
}
}
}
void dfs2(int u,int fa){
for (int j=head[u];j;j=e[j].pre){
int v=e[j].obj;
if (v!=fa){
dis2[v]=dis2[u]+e[j].c;
if (dis2[v]>dis2[t]) t=v;
dfs2(v,u);
}
}
}
void dfs3(int u,int fa){
for (int j=head[u];j;j=e[j].pre){
int v=e[j].obj;
if (v!=fa){
dis3[v]=dis3[u]+e[j].c;
ans=max(ans,min(dis3[v],dis2[v])+dis2[t]);
dfs3(v,u);
}
}
}
int main(){
n=read(); m=read();
rep(i,,m){
int x=read(),y=read();
ll z=read();
insert(x,y,z); insert(y,x,z);
}
dfs(,);
dfs2(s,);
dfs3(t,);
printf("%lld\n",ans);
return ;
}
上一篇:Dubbo入门到精通学习笔记(十四):ActiveMQ集群的安装、配置、高可用测试,ActiveMQ高可用+负载均衡集群的安装、配置、高可用测试


下一篇:Nginx 之五: Nginx服务器的负载均衡、缓存与动静分离功能