본문 바로가기

알고리즘 관련/BOJ

BOJ)2213 트리의 독립집합

문제: icpc.me/2213


트리에서 각 정점에 대한 가중치가 주어지고 정점들의 가중치를 최대로 가지는 최대독립집합 set을 구하는 문제이다.


트리에서의 최대 독립집합을 구하는 문제이기 때문에 사이클이 존재하지 않으므로 다이나믹 프로그래밍으로 해결할 수 있다.


dp[pos][state]로 pos번째 정점에 대한 선택여부를 state로 강제한다면 점화식을 쉽게 세워줄 수 있다.


해당 정점을 선택할 경우 해당 정점에 대한 가중치를 얻고 자식들은 state를 선택안함으로 강제된다.


해당 정점을 선택하지 않을 경우 자식들의 state 결과는 선택하거나 선택안하는 경우 중 최댓값을 가지게 된다.


두 케이스에 따라 점화식을 다르게 세워준 후 다이나믹 프로그래밍을 이용하여 답을 구해준 뒤 역추적을 해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
vector<vector<int>> vt, chd;
int n, g[10001], dp[10001][2], x, y, visited[10001];
pair<intint> back[10001][2];
vector<int> r;
void dfs(int here, int par) {
    visited[here] = 1;
    if (here != 1)chd[par].push_back(here);
    for (auto next : vt[here]) {
        if (!visited[next])
            dfs(next, here);
    }
}
int func(int pos, int state) {
    int &ret = dp[pos][state];
    if (ret != -1)return ret;
    ret = 0;
    if (state) {
        ret = g[pos];
        for (auto next : chd[pos])
            ret += func(next, 0);
    }
    else {
        for (auto next : chd[pos])
            ret += max(func(next, 1), func(next, 0));
    }
    return ret;
}
void ff(int pos, int state) {
    if (state) {
        r.push_back(pos);
        for (auto next : chd[pos])
            ff(next, 0);
    }
    else {
        for (auto next : chd[pos]) {
            if (dp[next][1>= dp[next][0])
                ff(next, 1);
            else
                ff(next, 0);
        }
    }
}
int main() {
    scanf("%d"&n);
    vt.resize(n + 1);
    chd.resize(n + 1);
    memset(dp, -1sizeof(dp));
    for (int i = 1; i <= n; i++)
        scanf("%d"&g[i]);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d"&x, &y);
        vt[x].push_back(y);
        vt[y].push_back(x);
    }
    dfs(10);
    int x = func(10);
    int y = func(11);
    if (x >= y)
        ff(10);
    else
        ff(11);
    printf("%d\n", max(x, y));
    sort(r.begin(), r.end());
    for (auto h : r)
        printf("%d ", h);
    return 0;
}
cs

 

'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1202 보석 도둑  (0) 2017.04.12
BOJ)14499 주사위 굴리기  (2) 2017.04.12
BOJ)3770 대한민국  (0) 2017.04.06
BOJ)6091 핑크 플로이드  (0) 2017.04.06
BOJ)1826 연료 채우기  (0) 2017.04.06