글 읽기 - scc의 개수에 관련해서..

again7536 4년 전 0

각 컴포넌트에서 scc는 1개 아닌가요?

그리고 scc를 1개의 노드로 압축하면 그 노드를 루트로 하는 트리가 생기죠?

그렇게 생각하고 knapsack으로 풀었는데 안되네요.. 혹시 scc가 여러개인가요?

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int T[2][1001];
int parent[1001];
bool visited[1001];
int group[1001];

struct Component {
	int root = 0;
	int cycle = 0;
	int num = 0;
	Component() {}
	Component(int r, int c, int n) : root(r), cycle(c), num(n) {}
};
bool compare(const Component* a, const Component* b) {
	if (a->cycle != b->cycle)
		return a->cycle < b->cycle;
	else return a->num < b->num;
}
Component component[1001]; //idx is root.
vector<Component*> comp;
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int n, k; cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> parent[i];

	for (int i = 1; i <= n; i++) {
		if (visited[i]) continue;
		int a = i, cnt = 0;
		while (!visited[a]) { visited[a] = true; a = parent[a]; cnt++; }
		if (group[a]) {
			int b = i;
			while (b != a) {
				group[b] = group[a];
				b = parent[b];
			}
			component[group[a]].num += cnt;
			continue;
		}
		int root = a, cycle = 1;
		while (parent[a] != root) { a = parent[a]; group[a] = root; cycle++; }
		int b = i;
		while (b != root) { group[b] = root; b = parent[b]; }
		group[root] = root;
		component[root] = Component(root, cycle, cnt);
		comp.push_back(&component[root]);
	}
	sort(comp.begin(), comp.end(), compare);
    
	for (int i = 0; i < comp.size(); i++) {
		for (int j = 1; j <= k; j++) {
			int temp = 0;
			if (j >= comp[i]->cycle) {
				if (j <= comp[i]->num) temp = j;
				else temp = comp[i]->num;
			}
			T[i % 2][j] = max(T[(i + 1) % 2][j], temp + T[(i + 1) % 2][j - temp]);
		}
	}

	cout << T[(comp.size() + 1) % 2][k];
}

again7536 4년 전 0

다른건 다 맞았는데, knapsack 부분을 저렇게 하면 안됐네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

scc의 개수에 관련해서..

again7536 4년 전 0

again7536 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말