试题历届试题大臣的旅费(c++)

秒速五厘米 2022-12-12 02:00 141阅读 0赞

代码是拷贝其他人的  
附链接：https://blog.csdn.net/the\_ZED/article/details/104174375?utm\_medium=distribute.pc\_relevant\_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.compare&depth\_1-utm\_source=distribute.pc\_relevant\_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.compare

思路：根据边的权值直接求图的直径？  
求直径的算法：任选一点，求最远的点  
在以最远的点求最远的点，这俩点就是直径

#include <iostream>
    #include <cmath>
    #include <algorithm>
    #include <cstdlib>
    #include <string>
    #include <cstring>
    #include <vector>
    using namespace std;
    const int maxn = 1e5 + 5;
    int maxFarNode;
    int maxlen = -1;
    bool vis[maxn];
    struct Node
    {
        
        int child, length;
        Node(int a, int b)
        {
        
            child = a, length = b;
        }
    };
    vector<Node> v[maxn];
    
    void dfs(int node, int nowlen)
    {
        
        if (vis[node]) return ;
        vis[node] = true;
        //遍历node的后继节点
        for (int i = 0; i < v[node].size(); i++)
        {
        
            int child = v[node][i].child;
            int length = v[node][i].length;
            if (vis[child]) continue;
            if (nowlen + length > maxlen)
            {
        
                maxlen = nowlen + length;
                maxFarNode = child;
            }
            dfs(child, nowlen + length);
        }
    }
    int main()
    {
        
        int  n;
        cin >> n;
        for (int  i = 1; i < n; i++)
        {
        
            int x, y, len;
            cin >> x >> y >> len;
            v[x].push_back(Node(y, len));
            v[y].push_back(Node(x, len));
        }
        dfs(1, 0);
        memset(vis, false, sizeof(vis));
        maxlen = -1;
        dfs(maxFarNode, 0);
        cout << maxlen * 10 + maxlen * (maxlen + 1) /2 << endl;
        system("pause");
        return 0;
    }