11554: 【原1554】naiveDP

题目

题目描述

author: yzh119 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1554

Description

给定一棵带边权有根树，要使得根节点与所有的叶子节点不相连，需要删去一些边，求要删去的边的边权和最小值。

Input Format

第一行两个整数\(n,root\)，表示节点的总数和根节点的编号（所有的节点的编号都属于1...n）。

接下来\(n - 1\)行，表示有根树的边，x y z表示x节点与y节点连有一条边权为z的边。

Output Format

输出要删去的边权和最小值。

Sample Input

5 5
2 4 1
4 1 1
3 5 2
5 4 3

Sample Output

4

Sample Input

9 2
5 1 4
3 4 2
4 8 1
3 6 1
2 3 5
1 2 4
4 9 0
3 7 1

Sample Output

7

Limits

对于\(100\%\)的数据，\(n\leq 800000\)。

对于\(30\%\)的数据，\(n \leq 10000\)。

所有的边权w都\(0 \leq w \leq 1e9\)。

yyong119's solution

#include <cstdio>
#include <queue>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX_N 800010
#define INF 0x7fffffff

struct node {
    int fpoint, tpoint, cost;
    node(int p, int q, int cc) {
        fpoint = p; tpoint = q; cost = cc;
    };
    node() {
        fpoint = 0; tpoint = 0; cost = 0;
    };
}tree[MAX_N << 1];

int start_index[MAX_N], par[MAX_N];
long f[MAX_N];
bool visited[MAX_N];

inline bool cmp(node p, node q) {
    return p.fpoint != q.fpoint ? p.fpoint < q.fpoint : p.tpoint < q.tpoint;
}

int main() {

    int n, root;
    scanf("%d%d", &n, &root);

    for (int i = 1; i < n; ++i) {
        int temp1, temp2, co;
        scanf("%d%d%d", &temp1, &temp2, &co);
        tree[i] = node(temp1, temp2, co);
        tree[i + n - 1] = node(temp2, temp1, co);
    }
    tree[(n << 1) - 1] = node(root, 0, INF);

    // In ascending order
    sort(tree + 1, tree + (n << 1), cmp);
    // Mark the start_index index of each node
    for (int i = (n << 1) - 1; i > 0; --i)
        start_index[tree[i].fpoint] = i;
    start_index[n + 1] = n << 1;

    visited[0] = true;
    queue<int> que;
    que.push(root);
    while (!que.empty()) {
        int cur = que.front(); que.pop();
        visited[cur] = true;
        // Indexes of cur
        for (int i = start_index[cur]; i < start_index[cur + 1]; ++i) {
            int next = tree[i].tpoint;
            if (visited[next]) // next is parent
                par[cur] = next;
            else { // next is child
                par[next] = cur;
                que.push(next);
            }
        }
    }

    memset(visited, false, sizeof(visited));
    visited[0] = true;

    stack<int> sta;
    sta.push(root); que.push(root);
    while (!que.empty()) {

        int cur = que.front(); que.pop();
        visited[cur] = true;
        // Indexes of node cur
        for (int i = start_index[cur]; i < start_index[cur + 1]; ++i)
            if (!visited[tree[i].tpoint]) {
                que.push(tree[i].tpoint);
                sta.push(tree[i].tpoint);
                visited[tree[i].tpoint] = true;
            }
    }

    while (!sta.empty()) {
        int cur = sta.top(); sta.pop();
        // Leaf node
        if (start_index[cur + 1] - start_index[cur] == 1)
            f[cur] = tree[start_index[cur]].cost;
        else {
            for (int i = start_index[cur]; i < start_index[cur + 1]; ++i)
                f[cur] += f[tree[i].tpoint] < tree[i].cost ? f[tree[i].tpoint] : tree[i].cost;
        }
    }

    printf("%d\n", f[root]);
    return 0;
}