首页 > 代码库 > 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