POJ-2631.Roads in the North(求树的直径)

小鱼儿 2022-02-05 10:59 203阅读 0赞

# [2631.Roads in the North][] #

### Description ###

Building and maintaining roads among communities in the far North is an expensive business. With this in mind, the roads are build such that there is only one route from a village to a village that does not pass through some other village twice.  
Given is an area in the far North comprising a number of villages and roads among them such that any village can be reached by road from any other village. Your job is to find the road distance between the two most remote villages in the area.

The area has up to 10,000 villages connected by road segments. The villages are numbered from 1.

### Input ###

Input to the problem is a sequence of lines, each containing three positive integers: the number of a village, the number of a different village, and the length of the road segment connecting the villages in kilometers. All road segments are two-way.

### Output ###

You are to output a single integer: the road distance between the two most remote villages in the area.

### Sample Input ###

5 1 6
    1 4 5
    6 3 9
    2 6 8
    6 1 7

### Sample Output ###

### 题意 ###

给出一棵树的两边结点，以及权重，求距离最远的两点之间的权重。

### 树形DP求树的直径 ###

这里面的dp数组保存的是x的子节点到x结点的最大距离

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    struct edge{ 
        int v,w;
        edge(int v,int w){ 
            this -> v = v;
            this -> w = w;
        }
    };
    vector<edge> vec[10001];
    int d[10001],ans; // d[x]表示x的子节点中最远的点到x的距离
    bool vis[10001];
    void dp(int u){ 
        vis[u] = 1;
        for(int i = 0;i < (int)vec[u].size();i++){ 
            int v = vec[u][i].v;
            if(vis[v]) continue;
            dp(v);
            ans = max(ans,d[u] + d[v] + vec[u][i].w);
            d[u] = max(d[u],d[v] + vec[u][i].w);
        }
    }
    int main(){ 
        /* freopen("test.txt","r",stdin); */
        int u,v,w;
        while(scanf("%d%d%d",&u,&v,&w) == 3){ 
            vec[u].push_back(edge(v,w));
            vec[v].push_back(edge(u,w));
        }
        dp(1);
        printf("%d\n",ans);
        return 0;
    }

### dfs求树的直径 ###

两次dfs，第一次dfs从1号点开始，找到距离1号点最远的点，第二次dfs从距离1号点最远的点开始，最终便得到两个距离最远的点。

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    struct edge{ 
        int v,w;
        edge(int v,int w){ 
            this -> v = v;
            this -> w = w;
        }
    };
    vector<edge> vec[10001];
    int d[10001],ans;
    bool vis[10001];
    int node; // 记录第一次dfs最远的点
    void dfs(int u,int s){ 
        vis[u] = 1;
        for(int i = 0;i < (int)vec[u].size();i++){ 
            int v = vec[u][i].v;
            int w = vec[u][i].w;
            if(vis[v]) continue;
            d[v] = s+ w;
            if(d[v] > ans){ 
                ans = d[v];
                node = v;
            }
            dfs(v,d[v]);
        }
    }
    int main(){ 
        freopen("test.txt","r",stdin);
        int u,v,w;
        while(scanf("%d%d%d",&u,&v,&w) == 3){ 
            vec[u].push_back(edge(v,w));
            vec[v].push_back(edge(u,w));
        }
        memset(vis,0,sizeof(vis));
        ans = 0;
        dfs(1,0);
        memset(vis,0,sizeof(vis));
        ans = 0;
        dfs(node,0);
        printf("%d\n",ans);
        return 0;
    }

### bfs求树的直径 ###

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    struct edge{ 
        int v,w;
        edge(int v,int w){ 
            this -> v = v;
            this -> w = w;
        }
    };
    vector<edge> vec[10001];
    int d[10001],ans;
    bool vis[10001];
    int node; // 记录第一次dfs最远的点
    void bfs(int u){ 
        queue<int> q;
        q.push(u);
        while(!q.empty()){ 
            int x = q.front();
            vis[x] = 1;
            q.pop();
            for(int i = 0;i < (int)vec[x].size();i++){ 
                int y = vec[x][i].v;
                if(vis[y]) continue;
                d[y] = d[x] + vec[x][i].w;
                if(d[y] > ans){ 
                    ans = d[y];
                    node = y;
                }
                q.push(y);
            }
        }
    }
    int main(){ 
        // freopen("test.txt","r",stdin);
        int u,v,w;
        while(scanf("%d%d%d",&u,&v,&w) == 3){ 
            vec[u].push_back(edge(v,w));
            vec[v].push_back(edge(u,w));
        }
        memset(vis,0,sizeof(vis));
        ans = 0;
        d[1] = 0;
        bfs(1);
        memset(vis,0,sizeof(vis));
        ans = 0;
        d[node] = 0;
        bfs(node);
        printf("%d\n",ans);
        return 0;
    }

[2631.Roads in the North]: http://poj.org/problem?id=2631