poj 1849 Two

/*poj 1849 two 思考一下会发现 就是求直径 直径上的中点就是两个人分开的地方(不再有交集)*/
#include<cstdio>
#define maxn 100010
using namespace std;
int n,num,head[maxn],root,f[maxn][],sum,M;
struct node{
int v,t,pre;
}e[maxn*];
int init(){
int x=,f=;char s=getchar();
while(s<''||s>''){if(s=='-')f=-;s=getchar();}
while(s>=''&&s<=''){x=x*+s-'';s=getchar();}
return x*f;
}
int max(int x,int y){
return x>y?x:y;
}
void Add(int from,int to,int dis){
num++;e[num].v=to;
e[num].t=dis;
e[num].pre=head[from];
head[from]=num;
}
void Cl(){
num=M=sum=;
for(int i=;i<=n;i++)
head[i]=f[i][]=f[i][]=;
}
void Dfs(int now,int from){
for(int i=head[now];i;i=e[i].pre){
int v=e[i].v;if(v==from)continue;
Dfs(v,now);
}
int mx=,mxx=;
for(int i=head[now];i;i=e[i].pre){
int v=e[i].v;if(v==from)continue;
int Mx=f[v][]+e[i].t;
if(Mx>mx)mxx=mx,mx=Mx;
else if(Mx>mxx)mxx=Mx;
}
f[now][]=mx;f[now][]=mxx;
}
int main()
{
while(~scanf("%d%d",&n,&root)){
Cl();
int u,v,t;
for(int i=;i<n;i++){
u=init();v=init();t=init();
Add(u,v,t);Add(v,u,t);sum+=t;
}
Dfs(root,);
for(int i=;i<=n;i++)
M=max(M,f[i][]+f[i][]);
printf("%d\n",sum*-M);
}
return ;
}
上一篇:android开发关于和使用本机内存、内置存储卡和外置存储卡 (转)


下一篇:freemarker中的substring取子串