취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24977번 문제인 Visits이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/24977 

모든 소는 정확히 한 마리의 소를 향해 가고싶어하므로 주어진 그래프는 directed pseudoforest로 생각할 수 있다.

이 directed pseudoforest에서, 사이클을 이루지 않는 간선에 대응되는 소의 움직임은 사이클을 이루고 있는 에지에 대응되는 소의 움직임에 아무런 영향을 주지 않게 모든 움직임을 실행할 수 있게끔 항상 permutation을 구성할 수 있다는 점을 관찰하자.

또한, 각 cycle에서도 단 하나의 움직임을 제외한다면 모든 움직임을 실행할 수 있게끔 항상 permutation을 구성할 수 있다는 점을 관찰하자.

따라서, 주어진 그래프에서, moo의 횟수를 최대화하려면 각 사이클마다 가장 적은 moo를 하는 움직임을 제외한 모든 움직임을 실행하면 된다.

주어진 pseudoforest에서 사이클을 탐색해나가며 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

pair<int, ll> G[100001];
int visited[100001]; // 0:방문함 1:방문함(사이클일 시 재방문안함) 2:방문함(사이클일 시 재방문함 / 사이클 가능성 없음)

ll dfs_cyc(int cur) {
	visited[cur] = 2;
	if (visited[G[cur].first] == 2) return G[cur].second;
	else return min(G[cur].second, dfs_cyc(G[cur].first));
}

ll dfs(int cur) {
	visited[cur] = 1;
	if (visited[G[cur].first] == 0) {
		ll ret = dfs(G[cur].first);
		visited[cur] = 2;
		return ret;
	}
	if (visited[G[cur].first] == 1) return dfs_cyc(G[cur].first);
	
	visited[cur] = 2;
	return 0; // visited[G[cur].first == 2
}

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

	ll ans = 0;

	int N; cin >> N;
	for (int i = 1; i <= N; i++) {
		int x; ll moo; cin >> x >> moo;
		ans += moo;
		G[i] = make_pair(x, moo);
	}

	for (int i = 1; i <= N; i++) {
		if (visited[i]) continue;
		ans -= dfs(i);
	}

	cout << ans;
}