티스토리 뷰

알고리즘 관련/BOJ

BOJ)10265 MT

JASON 자손9319 2017. 1. 24. 21:28

문제: icpc.me/10265


K이하의 사람이 버스에 탈 수 있을 때 버스에 탈 수 있는 최대 인원을 출력하는 문제이다.


문제에는 조건이 있는데 A라는 사람은 B라는 사람이 버스에 안타면 A도 반드시 안타는 정보 N개가 주어진다.


우리는 이러한 조건을 B->A라는 방향 그래프로 만들어 준 SCC끼리 분류를 한다음 다음 위상 정렬을 이용하여 


X라는 정점이 방문 가능한 모든점 Y는 반드시 X의 인원을 포함한다고 정의 가능하다.


이 때 X의 인원은 SCC의 그룹 크기와 동치가 된다.


따라서 연결 그래프마다 최소 인원~최대 인원 셋을 저장한 뒤 Knapsack문제를 해결하듯이 다이나믹 프로그래밍을 이용해주어 답을 계산해주면 된다.


이때 연결 그래프의 수는 SCC 그래프의 indegree가 0인 SCC의 개수이다.


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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>
#define MAX_N 1000
using namespace std;
int n, k, disc[MAX_N + 1], scc[MAX_N + 1], x, c, s, cost[MAX_N + 1], ma[MAX_N + 1], mi[MAX_N + 1], in[MAX_N + 1], dx[MAX_N + 1], dy[MAX_N + 1], r, dp[MAX_N + 1][MAX_N + 1];
vector<vector<int>> vt;
vector<vector<int>> svt;
stack<int> st;
int dfs(int here) {
    st.push(here);
    disc[here] = ++c;
    int ret = disc[here];
    for (int there : vt[here]) {
        if (!disc[there])
            ret = min(ret, dfs(there));
        else if (!scc[there])
            ret = min(ret, disc[there]);
    }
    if (ret == disc[here]) {
        s++;
        while (1) {
            int v = st.top();
            st.pop();
            scc[v] = s;
            cost[s]++;
            if (v == here)break;
        }
    }
    return ret;
}
int df(int here) {
    int ret = ma[here];
    for (int there : svt[here]) {
        ma[here] += ma[there];
        df(there);
    }
    return ret;
}
int knapsack(int pos, int val) {
    if (pos > r)
        return 0;
    int &ret = dp[pos][val];
    if (ret != -1)return ret;
    ret = knapsack(pos + 1, val);
    if (val >= dx[pos]) {
        for (int i = dx[pos]; i <= dy[pos]; i++) {
            if (i > val)
                break;
            ret = max(ret, knapsack(pos + 1, val - i) + i);
        }
    }
    return ret;
}
int main() {
    scanf("%d%d"&n, &k);
    vt.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d"&x);
        vt[x].push_back(i);
    }
    for (int i = 1; i <= n; i++)
        if (!disc[i])
            dfs(i);
    svt.resize(s + 1);
    for (int i = 1; i <= n; i++) {
        for (int next : vt[i]) {
            if (scc[next] == scc[i])
                continue;
            svt[scc[i]].push_back(scc[next]);
            in[scc[next]]++;
        }
    }
    for (int i = 1; i <= s; i++)
        ma[i] = mi[i] = cost[i];
    for (int i = 1; i <= s; i++
            df(i);
    for (int i = 1; i <= s; i++) {
        if (!in[i]) {
            dx[++r] = mi[i];
            dy[r] = ma[i];
        }
    }
    memset(dp, -1sizeof(dp));
    printf("%d\n", knapsack(1, k));
    return 0;
}
cs


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

BOJ)2512 예산  (0) 2017.01.25
BOJ)1576 DNA점수  (0) 2017.01.25
BOJ)10265 MT  (0) 2017.01.24
BOJ)3977 축구 전술  (0) 2017.01.24
BOJ)4196 도미노  (0) 2017.01.24
BOJ)3665 최종 순위  (2) 2017.01.22
댓글
댓글쓰기 폼