首页 > 代码库 > POJ2631 Roads in the North
POJ2631 Roads in the North
题解:
树的最长路径,根据树的最长路径的性质,从任一一点bfs得到最远的点的位置,然后再从该点重新bfs一次就可以得到树的直径了
数学证明http://www.cnblogs.com/wuyiqi/archive/2012/04/08/2437424.html
代码:
#include<iostream>#include<cstdio>#include<vector>#include<cstring>#include<cmath>#include<queue>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define ll long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x)) #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 #define INF 2097152typedef pair<int,int> P;const double eps=1e-9;const int maxn=10100;const int mod=1e9+7;struct Node{ int v,w,nxt;};Node edges[maxn*2];int head[maxn],dis[maxn],vis[maxn];int goal,cnt,max_length;void Addedge(int u,int v,int w){ edges[cnt].v=v; edges[cnt].w=w; edges[cnt].nxt=head[u]; head[u]=cnt++;}int bfs(int u){ memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); queue<int> q; q.push(u); vis[u]=1; while(!q.empty()){ int now=q.front(); q.pop(); for(int i=head[now];i!=-1;i=edges[i].nxt){ int v=edges[i].v; if(!vis[v]){ dis[v]=dis[now]+edges[i].w; q.push(v); vis[v]=1; } if(dis[v]>max_length){ max_length=dis[v]; goal=v; } } } return max_length;}int main(){ memset(head,-1,sizeof(head)); cnt=0; max_length=0; int u,v,w; while(~scanf("%d%d%d",&u,&v,&w)){ Addedge(u,v,w);Addedge(v,u,w); } bfs(1); printf("%d\n",bfs(goal));}
POJ2631 Roads in the North
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。