首页 > 代码库 > 蓝桥杯 大臣的旅费_树的最长度_两次DFS

蓝桥杯 大臣的旅费_树的最长度_两次DFS

#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <functional>#include <vector>using namespace std;const int maxn = 1000000 + 10;const int INF = 10000000;int n;bool used[maxn];vector<int> G[maxn];vector<int> E[maxn];     //int d[maxn];void init() {    memset(used, 0, sizeof(used));}void dfs(int u){    used[u] = true;        int size = G[u].size();        for (int i = 0; i < size; i++)    {        int v = G[u][i];            //得到这个点的临边        if (!used[v]) {            d[v] = d[u] + E[u][i];  //走临边的情况            dfs(v);                 //dfs()临边         }    }}void solve(){    cin >> n;        int u, v, w;        for (int i = 0; i < n - 1; i++) {        scanf("%d%d%d", &u, &v, &w);        G[u - 1].push_back(v - 1);        E[u - 1].push_back(w);                G[v - 1].push_back(u - 1);        E[v - 1].push_back(w);    }        //第一遍    init();    fill(d, d + n, INF);    d[0] = 0;        //递归找到最远路     dfs(0);    int start = 0;        //得到最大值的下标     int max = -1;        //为了找到最远路     for (int i = 0; i < n; i++)    {        if (d[i] > max && d[i] != INF) {  //走过             max = d[i];            start = i;    //找到最远路         }    }        //http://blog.csdn.net/chao1983210400/article/details/26447001    //树的最长路求法:两次dfs,从任意点出发一次dfs找到的最远结点A,再从A开始进行一次dfs找到的最远点既为树的的直径。    //第二遍     //从最远路出发,dfs找到的最远点一定是树的直径     //现有结论,从任意一点u出发搜到的最远的点一定是s、t中的一点,然后在从这个最远点开始搜,就可以搜到另一个最长路的端点,    //即用两遍广搜就可以找出树的最长路    init();    for (int i = 0; i < n; i++) {        d[i] = (i == start ? 0 : INF);    }    dfs(start);             int ans = -1;    for (int i = 0; i < n; i++) {        if (d[i] > ans && d[i] != INF) {            ans = d[i];        }    }        ans = 10 * ans + ans * (ans + 1) / 2;        cout << ans << endl;    }int main(){    solve();    return 0;}

 

蓝桥杯 大臣的旅费_树的最长度_两次DFS