BOJ)10265 MT

문제: icpc.me/10265

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

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

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

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

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

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

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

#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, -1, sizeof(dp));
    printf("%d\n", knapsack(1, k));
    return 0;
}