Skip to content

11082: 【原1082】二哥的鹅塘

题目

题目描述

author: duruofei 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1082

Description

“鹅鹅鹅”事件过后,二哥为他的鹅们建立了庞大的鹅塘。

二哥的鹅塘有很多小水池,水池之间有河道相连。

抽象地说,二哥的鹅塘可以看成一个具有N个结点的连通的无环无向图。

鹅塘有且仅有一个入口,包括入口在内,图上每一个节点(对应鹅塘每一个水池)都住着一群鹅。

如果二哥每天都亲自看管这些鹅,他就很难抽空再写code了,于是二哥决定雇佣TA!

遗憾的是,被放置在 i 点的TA只能监督 i 点所代表的水池中的鹅, i 的父节点所代表水池中的鹅以及 i 的所有儿子结点所代表的水池上的鹅。

如图,如果在结点2放置TA,那么结点1、2、5、6中的鹅可以被监督到。

然而,在第i个节点上放置TA是要付出 w[i] 的资金的。如图,在结点2上放置TA需要花费16。

二哥最近手头实在很紧,于是乎,二哥找到了聪明的你,想让你帮他设计一个既能监督到所有鹅,又能保证花费的资金最少的方案。

Input Format

第1行一个正整数 n,表示鹅塘中水池的数目。

第2行至第 n+1 行,每行描述每个结点所代表的水池的信息,依次为:

该结点标号i(\(0 < i \leq n\)),在该点安排TA所需的经费k,该点的儿子个数 c,接下来 c 个数,分别是这个节点的 c 个儿子的标号r1,r2,...,rc。

对于一个n(\(0 < n \leq 100000\))个结点的鹅塘,结点标号在1到n之间,且标号不重复。

Output Format

请输出一个数,为所求的最少的经费。

Hint

对于100分的数据,\(0 < N \leq 100000\)

数据中存在链、完全二叉树、多叉树等多种多样的情况,但本题数据依然很弱,难度系数依然很低。O(∩_∩)O~

Sample Input

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

Sample Output

25

FineArtz's solution

/* 二哥的鹅塘 */
#include <iostream>
#include <set>
using namespace std;

const int INF = 2147483647;

class Node{
public:
    int w = 0;
    set<int> child;
};

Node a[100005];
int n, root = 0;
int f[100005][3] = {0};
bool b[100005] = {0};

void dp(int x){
    int t = INF;
    for (int i : a[x].child){
        dp(i);
        f[x][0] += min(min(f[i][0], f[i][1]), f[i][2]);
        f[x][1] += min(f[i][0], f[i][1]);
        f[x][2] += min(f[i][0], f[i][1]);
        t = min(t, f[i][0] - min(f[i][0], f[i][1]));
    }
    f[x][0] += a[x].w;
    f[x][1] += t;
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; ++i){
        int x, w, c;
        cin >> x >> w >> c;
        a[x].w = w;
        for (int i = 1; i <= c; ++i){
            int y;
            cin >> y;
            a[x].child.insert(y);
            b[y] = true;
        }
    }
    for (int i = 1; i <= n; ++i){
        if (!b[i]){
            root = i;
            break;
        }
    }
    dp(root);
    cout << min(f[root][0], f[root][1]) << endl;
    return 0;
}