14223: 【原4223】枯萎的树

题目描述

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

Description

从前有棵树。一棵有n个节点的树(节点标号1~n)。现在树上有一些边枯萎了。为了救活这棵树，zwx希望在树上某些节点滴加营养液，使得从该节点到根节点的所有枯萎的边恢复正常。根节点的编号默认为1。众所周知，滴加营养液数较少的方案一定更优。在此基础上，营养液流经边数较少的方案较优。现在希望你找到一个最优的方案，输出最少的营养液滴数以及其作用节点(按节点标号从小到大排列)。

Input Format

第一行一个整数n。接下来n-1行每行3个整数，i，j，k，为节点i与j之间有一条边，k=1正常，k=2枯萎。

Output Format

第一行一个整数表示营养液滴数x，第二行x个整数表示作用节点。

Sample Input

Sample Output

4
2 3 4 5

Limit

对于\(40%\)的数据，\(n \leq 10^4\)

对于\(100%\)的数据，\(n \leq 10^5\)

ligongzzz's solution

#include <iostream>
#include <vector>
using namespace std;

class node {
public:
    int parent = 0;
    vector<int> child;
    vector<int> isbad;
    bool good = false;
};

int n;
vector<node> tdata;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    tdata.resize(n + 1);

    for (int a = 0; a < n; ++a) {
        int i, j, k;
        cin >> i >> j >> k;

        tdata[i].child.emplace_back(j);
        tdata[j].child.emplace_back(i);

    }

    return 0;
}

zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n;
int to[200005], at[100005] = {0}, nxt[200005], cnt = 0, id[200005] = {0}, tot = 0;
bool used[100005] = {0};
bool dfs(int cur, int fa){
    bool ans = false;
    for (int i = at[cur]; i; i = nxt[i]){
        if(to[i] == fa) continue;
        bool res = dfs(to[i], cur);
        if(id[i] == 2){
            if(!res) used[to[i]] = ans = true, tot++;
            else ans = true;
        }else{
            if(res) ans = true;
        }
    }
    return ans;
}
void init(){
    n = read();
    for (int i = 1; i < n; ++i){
        int u = read(), v = read(), st = read();
        to[++cnt] = v, nxt[cnt] = at[u], id[cnt] = st, at[u] = cnt;
        to[++cnt] = u, nxt[cnt] = at[v], id[cnt] = st, at[v] = cnt;
    }
}
void solve(){
    dfs(1, 0);
    printf("%d\n", tot);
    for (int i = 1; i <= n; ++i)
        if(used[i]) printf("%d ", i);
}
int main(){
    init();
    solve();
    return 0;
}