UVa 10308 Roads in the North：树上的最长路

10308 - Roads in the North

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1249

思路：由于是一棵树，我们只要随便指定一个树根就开始dfs。所有路径都可以看成以父节点为中转点的“子树甲+子树乙”的形式（只有一个子树的情况也是一样的），遍历时向上返回一个最大的路径长即可。

完整代码：

/*0.016s*/

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005;  

char s[30];
int ans;
vector<pair<int, int> > node[maxn]; /// first: 与node[i]连结的村庄号  second: 距离  

int dfs(int to, int from)
{
    int lto, lans = 0, lmax = 0;
    for (int i = 0; i < node[to].size(); ++i)
    {
        lto = node[to][i].first;
        if (lto != from)
        {
            lans = dfs(lto, to) + node[to][i].second;///递归子树，返回子树中的最长路
            ans = max(ans, lans + lmax);///当前得到的子树最长路和前面得到的另一棵子树的最长路之和
            lmax = max(lmax, lans);
        }
    }
    return lmax;
}  

int main()
{
    int u, v, l, i;
    bool ok = true;
    while (ok)
    {
        for (i = 0; i < maxn; ++i) node[i].clear();
        while (true)
        {
            if (gets(s) == 0)
            {
                ok = false;
                break;
            }
            if (s[0])
            {
                sscanf(s, "%d%d%d", &u, &v, &l);
                node[u].push_back(make_pair(v, l));
                node[v].push_back(make_pair(u, l));
            }
            else break;
        }
        ans = 0;
        dfs(1, 0);
        printf("%d\n", ans);
    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索递归
， int
， node
， 路径
， 一个
最长
uva ms in commerce、the silk roads、the two roads、the toll roads、the silk roads 微盘，以便于您获取更多的相关知识。