ACM – UVA10308 – 无根树转有根树

点击量:29

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

利用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 = 0; 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 = 0, lans = 0, lto;
    for(int i = 0; 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 = 0; i < maxn; i++) node[i].clear();
        while(1)
        {
            if(gets(s) == 0)
            {
                c = 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;
        ds(1, 0);
        printf("%d\n", ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注