input
u1 v1 w1
u2 v2 w2
...
un vn wn 1<=vi,ui<=n+1
/n
output
距离最远的两个点的距离
做法：一颗全连通且只有一条路从一个顶点到达另一个顶点，直接深搜，返回时返回最远的支路，且最远的支路加上第二远的支路和总路途最远比较，更新总路途最大，因为以一个点为中心走很多条路，最远的肯定是最大两条路的和，做法类似dp
输入有点坑，输完最后一组数据直接EOF，处理输入搞了好久，gets返回的是指针，遇到EOF返回NULL，遇空白行字符串第一个字符为NULL结束符，返回指针不为NULL
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include<cstring>
#define MAX 10010 using namespace std; struct node
{
vector<int>next,dis;
}; node tree[MAX];
int vis[MAX],maxd; int dfs(int x)
{
int max1=,max2=;
vector <int>dis;
vector<int>::iterator i,j,k;
for(i=tree[x].next.begin(),j=tree[x].dis.begin();i!=tree[x].next.end();i++,j++)
if(!vis[*i])
{
vis[*i]=;
dis.push_back(dfs(*i)+*j);
}
if(dis.empty()) return ;
for(k=i=dis.begin();i!=dis.end();i++)
if(max1<*i)
{
max1=*i;
k=i;
}
for(j=dis.begin();j!=dis.end();j++)
if(max2<*j&&j!=k) max2=*j;
maxd=max(maxd,max1+max2);//最远的和第二远的相加更新最远
//printf("maxd=%d max1=%d max2=%d\n",maxd,max1,max2);
return max1;//返回最远的
} void init()
{
memset(vis,,sizeof(vis));
for(int i=;i<MAX;i++)
{
tree[i].next.clear();
tree[i].dis.clear();
}
maxd=-;
}
int main()
{
//freopen("/home/user/桌面/in","r",stdin);
int a,b,c;
char s[];
init();
while()
{
char*p=gets(s);
//printf("p=%p\n",p);
if(s[]&&p)
{
//printf("s[0]=%d\n",s[0]);
//printf("1s[0]=%d\n",s[0]);
sscanf(s,"%d%d%d",&a,&b,&c);
tree[a].next.push_back(b);
tree[a].dis.push_back(c);
tree[b].next.push_back(a);
tree[b].dis.push_back(c);
}
else
{
/*printf("cal:s[0]=%d\nmaxd=%d\nvis[1]=%d\n",s[0],maxd,vis[1]);
for(int i=1;i<=6;i++)
for(int j=0;tree[i].next.begin()+j!=tree[i].next.end();j++)
printf("%d:%d %d\n",i,tree[i].next[j],tree[i].dis[j]);*/
//printf("s[0]=%d\n",s[0]);
vis[]=;
maxd=max(maxd,dfs());
printf("%d\n",maxd);
init();
if(p==NULL) break;
}
}
return ;
}