POJ_1985_Cow Marathon(树的直径)

题型：图论

题意：求解树上最长路，即树的直径

分析：

       两次BFS，首先随意找个起点，BFS出距离该点最远的点，然后以这个点为起点再一次BFS找出最远的点至其距离即为树的直径。

代码：

#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdio>
#define mt(a,b) memset(a,b,sizeof(a));
using namespace std;

const int M = 45678;
int n,m;

struct G {
    struct E {
        int u,v,w,next;
    } e[M*4];
    int le,head[M];
    void init() {
        le=0;
        mt(head,-1);
    }
    void add(int u,int v,int w) {
        e[le].u=u;
        e[le].v=v;
        e[le].w=w;
        e[le].next=head[u];
        head[u]=le++;
    }
} g;

int longest;
int dis[M];
bool used[M];
int bfs(int start) {
    mt(dis,-1);
    dis[start] = 0;
    mt(used,false);
    queue<int> q;
    q.push(start);
    used[start] = true;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i=g.head[u]; ~i; i=g.e[i].next) {
            int v = g.e[i].v;
            int w = g.e[i].w;
            if(dis[v] < dis[u] + w && !used[v]) {
                dis[v] = dis[u] + w;
                q.push(v);
                used[v] = true;
            }
        }
    }
    longest = -1;
    int point = -1;
    for(int i=1; i<=n; i++) {
        if(longest < dis[i]) {
            longest = dis[i];
            point = i;
        }
        longest = max(longest,dis[i]);
    }
    return point;
}

int main() {
    while(~scanf("%d%d",&n,&m)) {
        g.init();
        int u,v,w;
        char d[5];
        for(int i=0; i<m; i++) {
            scanf("%d%d%d%s",&u,&v,&w,d);
            g.add(u,v,w);
            g.add(v,u,w);
        }

        int id = bfs(1);

//        for(int i=1;i<=n;i++){
//            printf("%d ",dis[i]);
//        }
//        puts("");

        id = bfs(id);
        printf("%d\n",dis[id]);

    }
    return 0;
}