poj 1985 Cow Marathon

点击打开poj 1985

思路: 两次bfs找到树的直径
分析:
1 题目给定一棵树，找树上两点最远距离
2 利用两次bfs就可以，第一次bfs从1开始求出到最远的点，然后从这个点再次bfs回来求出ans即可

代码:

#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 50010;

struct Node{
    int x;
    int dis;
};

int n , m;
int ans , start;
vector<int>mat[MAXN];
vector<int>val[MAXN];
bool vis[MAXN];
queue<Node>q;

void bfs(){
    while(!q.empty()){
        Node tmp = q.front();
        q.pop();
        bool isNext = false;
        int x = tmp.x;
        int size = mat[x].size();
        for(int i = 0 ; i < size ; i++){
            if(!vis[mat[x][i]]){
                vis[mat[x][i]] = true;
                q.push((Node){mat[x][i] , tmp.dis+val[x][i]});
                isNext = true;
            }
        }
        if(!isNext){
           if(ans < tmp.dis){
               ans = tmp.dis;
               start = tmp.x;
           }
        }
    } 
}

int getAns(){
    memset(vis , false , sizeof(vis));
    vis[1] = true;
    q.push((Node){1 , 0});
    ans = 0;
    bfs();
    
    memset(vis , false , sizeof(vis));
    vis[start] = true;
    q.push((Node){start , 0});
    bfs();
    return ans;
}

void init(){
    for(int i = 0 ; i < MAXN ; i++){
        mat[i].clear();
        val[i].clear();
    }
}

int main(){
    char c;
    int x , y , v;
    while(scanf("%d%d" , &n , &m) != EOF){
         init();
         while(m--){
              scanf("%d %d %d %c" , &x , &y , &v , &c);
              mat[x].push_back(y);
              mat[y].push_back(x);
              val[x].push_back(v);
              val[y].push_back(v);
         }
         printf("%d\n" , getAns());
    }
    return 0;
}