ACM – UVA10308 – 无根树转有根树

比较莫名奇妙的题目,明明是搜索题目居然放在了数学分类,完全找不到数学的影子。。

利用vector,遍历树,找出最大的子树路径,然后与次大的子树路径相加即为答案。

因为图表示这方面太渣,基本上抄袭了别人的代码= =

#include <bits/stdc++.h>
using namespace std;
// 大数,内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = ; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
const int maxn = 1e5 + 10;
vector < pair <int, int> > node[maxn];
int ans;
int ds(int to, int from)
{
    int lmax = , lans = , lto;
    for(int i = ; i < node[to].size(); i++)
    {
        lto = node[to].at(i).first;
        if(lto != from)
        {
            lans = ds(lto, to) + node[to].at(i).second;
            ans = max(ans, lans + lmax);
            lmax = max(lmax, lans);
        }
    }
    return lmax;
}
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    char s[20];
    bool c = true;
    int u, v, l;
    while(c)
    {
        for(int i = ; i < maxn; i++) node[i].clear();
        while(1)
        {
            if(gets(s) == )
            {
                c = false;
                break;
            }
            if(s[])
            {
                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 = ;
        ds(1, );
        printf("%d\n", ans);
    }
    return ;
}
Licensed under CC BY-NC-SA 4.0
comments powered by Disqus
使用 Hugo 构建
主题 StackJimmy 设计