放牧代码和思想
专注自然语言处理、机器学习算法
    This thing called love. Know I would've. Thrown it all away. Wouldn't hesitate.

UVa 12161 Ironman Race in Treeland 题解《挑战程序设计竞赛》

目录

hankcs.com 2017-02-01 下午11.23.32.png挑战程序设计竞赛第二版.jpg

UVa 12161 Ironman Race in Treeland 

赛车:给定一颗树及各边长度及花费,请计算花费在m以内的最长路径。hankcs.com 2017-02-01 下午11.23.32.png

4.6划分、解决、合并:分治法 

树上的分治法 

不断根据重心分割子树,将包含子树根节点的路径记录到path中。记已经处理过的路径集合为b,未处理的路径集合为e。那么经过子树根节点的路径一定部分来自b,另一部分来自e。

Ironman Race in Treeland.png

然后设法遍历组合b和e即可。直接枚举并不现实,对b和e分别按花费排序,删除那些花费大长度反而小的路径。那么固定b中的一个元素,e中倒数第一个使得b+e花费不超过m的路径组合即为子树的答案。

书上的模板太坑爹了,光重心分割别的什么都不做提交上去都TLE。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;
#define MAX_N 30004

struct edge
{
    int to, damage, length, next;
};
int G[MAX_N], edge_size, n, m;
edge E[MAX_N * 2];

void add_edge(int from, int to, int damage, int length)
{
    edge e = {to, damage, length, G[from]};
    E[edge_size] = e;
    G[from] = edge_size++;
}

int ans, pre_max_subtree_size, pre_subtree_size;
int subtree_size[MAX_N];
bool V[MAX_N];

//查找重心的递归函数
//在以v为根的子树中寻找一个顶点,使得删除该顶点后最大子树的顶点数最小
void search_centroid(int v, int p, int &root)
{
    int max_subtree_size = 0;
    subtree_size[v] = 1;
    for (int j = G[v]; ~j; j = E[j].next)
    {
        int to = E[j].to;
        if (to == p || V[to])
            continue;
        search_centroid(to, v, root);
        if (subtree_size[to] > max_subtree_size)
            max_subtree_size = subtree_size[to];
        subtree_size[v] += subtree_size[to];
    }
    if (pre_subtree_size - subtree_size[v] > max_subtree_size)
        max_subtree_size = pre_subtree_size - subtree_size[v];
    if (max_subtree_size < pre_max_subtree_size)
        root = v, pre_max_subtree_size = max_subtree_size;
}

//计算子树大小(subtree_size)的递归函数
int compute_subtree_size(int v, int p)
{
    int ans = 1;
    for (int j = G[v]; ~j; j = E[j].next)
    {
        int to = E[j].to;
        if (to == p || V[to])
            continue;
        ans += compute_subtree_size(to, v);
    }
    return ans;
}

pair<int, int> path[MAX_N];
int b, e;

//计算子树中的所有顶点到重心的距离
void enumerate_paths(int v, int p, int damage, int length)
{
    path[e++] = {damage, length};
    for (int j = G[v]; ~j; j = E[j].next)
    {
        int to = E[j].to;
        if (to == p || V[to])
            continue;
        if (damage + E[j].damage <= m)
        {
            enumerate_paths(to, v, damage + E[j].damage, length + E[j].length);
        }
    }
}

// 删除长度小,花费大的路径
void remove_useless(int b, int &e)
{
    if (b == e)
        return;
    int size;
    for (int i = size = b + 1; i < e; i++)
    {
        if (path[i].first == path[size - 1].first)
            continue;
        if (path[i].second <= path[size - 1].second)
            continue;
        path[size++] = path[i];
    }
    e = size;
}

void solve_sub_problem(int v, int p)
{
    for (int j = G[v]; ~j; j = E[j].next)
    {
        int to = E[j].to;
        if (to == p || V[to])
            continue;
        pre_max_subtree_size = MAX_N;
        pre_subtree_size = compute_subtree_size(to, v);
        int root;
        search_centroid(to, v, root);
        V[root] = 1;
        solve_sub_problem(root, v);
        V[root] = 0;
    }
    b = e = 0;
    for (int j = G[v]; ~j; j = E[j].next)
    {
        int to = E[j].to;
        if (to == p || V[to])
            continue;
        if (E[j].damage <= m)
        {
            enumerate_paths(to, v, E[j].damage, E[j].length);
        }
        if (b > 0)
        {
            sort(path + b, path + e);
            remove_useless(b, e);
            for (int b_ = 0, e_ = e - 1; b_ < b; b_++)
            {
                while (e_ >= b && path[b_].first + path[e_].first > m)
                    e_--;
                if (e_ >= b)
                    ans = max(ans, path[b_].second + path[e_].second);
            }
        }
        sort(path, path + e);
        remove_useless(0, e);
        b = e;
    }
}

int solve()
{
    int root;
    pre_max_subtree_size = MAX_N, pre_subtree_size = n;
    search_centroid(1, -1, root);
    V[root] = 1;
    solve_sub_problem(root, -1);
    return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("err.txt", "w", stderr);
#endif
    int T, t = 1;
    scanf("%d", &T);
    while (T--)
    {
        ans = 0;
        edge_size = 0;
        memset(G, -1, sizeof(G));
        memset(V, 0, sizeof(V));
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n - 1; i++)
        {
            int u, v, damage, length;
            scanf("%d%d%d%d", &u, &v, &damage, &length);
            --u, --v;
            add_edge(u, v, damage, length);
            add_edge(v, u, damage, length);
        }
        printf("Case %d: %d\n", t++, solve());
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stderr);
#endif
    return 0;
}

hankcs.com 2017-02-01 下午11.20.41.png

Reference

https://github.com/pkkj/ACM-ICPC-OJ-Code/blob/344b2c92f75b428d0241ba732c43de780d08df40/ICPC.Regional/2008.Kuala_Lumpur/2008.Kuala_Lumpur.Solution_CN.md#problem-g-ironman-race-in-treeland

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » UVa 12161 Ironman Race in Treeland 题解《挑战程序设计竞赛》

评论 4

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #2

    我感觉您没有考虑root出发的路径谢谢

    我就爱睡-8年前 (2017-03-05)回复
    • 感谢指正,改为solve_sub_problem(root, -1);即可

      hankcs8年前 (2017-03-05)回复
  2. #1

    您好
    这组数据udebug和您的程序都出了十三,但是1->2->4是15,如果能解释一下题意的话感激不尽谢谢。
    1
    12 8
    1 2 5 8
    1 3 2 2
    2 4 2 7
    2 5 6 4
    2 6 1 3
    3 7 4 7
    3 8 4 2
    3 9 5 4
    3 10 7 2
    7 11 1 5
    7 12 6 8

    我就爱睡-8年前 (2017-03-05)回复

我的作品

HanLP自然语言处理包《自然语言处理入门》