백준 10265 MT

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

10265번: MT

Solved.ac에서는 문제에 SCC태그를 달아놔서 쫄았는데, 풀어 보니 필요 없었다. P4라는 난이도도 부풀려진게 아닐까.

 

풀이로 넘어가서, 문제 상황만 보면 x_i를 데려가야 i를 데려갈 수 있기에, x_i에서 i로 간선을 연결하고 위상정렬을 하고 싶어진다. SCC가 있을 테니, 그걸 잘 처리하면 될 거 같다고 생각하게 된다.

이제 그래프의 형태를 관찰하면, In-degree가 하나니까 사이클이 하나 있고, 거기서 뻗어나가는 그래프가 만들어진다. 

그 예시로 문제의 두번째 TC에 대한 그림은 다음과 같다.

즉, 이 사이클 전체가 버스에 타면 해당 컴포넌트에서 나머지 사람들은 원하는 수만큼 버스에 태울 수 있고, 아니라면 이 컴포넌트의 사람은 아예 태울 수 없다.

그러면 해당 컴포넌트의 크기와, 해당 컴포넌트에서 사이클의 크기를 알면 문제를 해결할 수 있을 것이다. 컴포넌트의 크기는 Disjoint Set으로 구한다. 사이클의 크기는, 위에서 만든 그래프를 뒤집고 위상정렬을 하면 남는게 사이클이기 때문에 그 크기를 구할 수 있다.

(즉, 애초에  x_i에서 i로 간선을 연결할 필요 없이 i에서 x_i로 간선을 연결하면 된다! 필자의 사고 흐름을 정리한 것이기 때문에 위의 그래프가 나왔지만, 반대 그래프를 그려야 문제를 해결할 수 있다는 것이다. 물론 필자와 다른 방법(DFS 등)으로 사이클을 찾을 경우 위의 그래프를 활용하는 것이 더 좋을 때도 있겠다.)

 

이제 마지막으로 답을 구하기 위해서는 [n][k]짜리 일종의 knapsack DP를 하면 된다. i번째 컴포넌트까지 확인하고, j명을 태워야 할 때 태울 수 있는 사람의 수의 최대값을 저장하는 것이다. 

각각의 컴포넌트에 대해, 그 크기를 sz[i], 사이클 크기를 cyc[i]라 두면, 아래와 같은 점화식을 얻을 수 있다. i번째 컴포넌트의 사이클을 가져가거나, 가져가지 않을 수 있기 때문이다.

DP[i][j]=max(DP[i-1][j-cyc[i]]+sz[i], DP[i-1][j])

해당 DP를 수행하고, 마지막으로 데려갈 수 있는 사람의 수를 구할 때는 DP[n][j]의 최대값을 확인하면 답을 얻을 수 있다.