POJ2631 Roads in the North

题面:http://poj.org/problem?id=2631

本题是求树的直径裸题。Code:
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAXN=10005;
struct Node{int v,Next,w;
}Edge[MAXN*2];
int head[MAXN],maxDis,Cnt,maxInd;
void Push(int u,int v,int w){++Cnt;Edge[Cnt].v=v;   Edge[Cnt].w=w;Edge[Cnt].Next=head[u];head[u]=Cnt;
}
void dfs(int now,int fa,int dis){if(dis>maxDis){maxDis=dis;maxInd=now;}for(int i=head[now];i;i=Edge[i].Next){if(Edge[i].v!=fa){dfs(Edge[i].v,now,Edge[i].w+dis);}}
}
int main(){int u,v,w;while(~scanf("%d%d%d",&u,&v,&w)){Push(u,v,w);Push(v,u,w);}dfs(1,0,0);dfs(maxInd,0,0);printf("%d\n",maxDis);return 0;
}

转载于:https://www.cnblogs.com/ukcxrtjr/p/11243509.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！