Informatica Online Judge

  병원균 퇴치 2 [1045 / 0415]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 5   Total Tried : 16


The Champion of this Problem (C++) : gs19030 - 0ms / 1087byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

경곽이는 병원균에 대해서 계속 연구하고 있다.

병원균은 N개의 세포와 M개의 세포간 전달물질로 구성되어 있다.

병원균의 활성도는 연결된 세포들의 개수로 결정된다. 만약 N개의 세포가 모두 연결되어 있다면 이 때 활성도는 N이다.

만약 N개의 세포가 2그룹으로 나뉘어 있으며, 하나의 그룹은 N-c개 다른 그룹은 c개의 세포가 서로 연결되어 있다면, 이 때 활성도는 각각 그룹 별로 N-c, c가 된다.

경곽이는 병원균의 활성도를 최대한 낮추기 위하여 병원균의 연결통로를 제거할 수 있는 기술을 개발했다. 그러나 아직 기술이 완벽하지 못하여, 한 번에 한 개씩만 제거할 수 있다.

이 병원균은 워낙 복원력이 강해서, 연결통로가 제거되면 연결된 세포들끼리 통신하여 바로 연결통로를 복원한다.

하지만 제거된 연결통로로 인하여 병원균이 두 그룹으로 나뉘게 되면, 서로 통신을 할 수가 없어 이 연결통로를 복원하지 못하고 2그룹으로 분할된다.

경곽이는 이 점을 최대한 이용하여 이러한 연결통로를 위크포인트라 부르기로 했다.

경곽이는 병원균의 위크포인트를 찾아서 이를 제거함으로 해서 병원균을 약화시킬 수 있다.

경곽이가 위크포이트를 제거할 때, 그 병원균 그룹의 활성도만큼의 비용이 필요하다. 만약 3개의 세포로 구성된 그룹에서 위크포인트를 제거하기 위해서는 비용 3이 필요하다.

경곽이의 목적은 모든 위크포인트를 제거하여 최대한 병원균을 많은 그룹으로 분할하여 최대 활성도를 낮추는데 있다.

여기서 경곽이는 재미있는 사실을 알게되었다.

위크포인트가 3개가 있다면, 이 위크포인트를 제거하는 순서를 1, 2, 3으로 할 때와 3, 1, 2로 할 때, 2, 1, 3으로 할 때 등, 제거하는 순서를 달리하면 드는 비용이 달라짐을 알게되었다.

병원균의 정보가 주어질 때, 모든 병원균을 최대한 작은 그룹으로 모두 분할하기 위하여 드는 최소비용을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 세포의 수 N과 세포간 통로 M이 공백으로 구분되어 입력된다.
두 번째 줄부터 M줄에 걸쳐서 세포간 통로가 연결하는 세포의 번호가 공백으로 구분되어 입력된다.

[입력값의 정의역]
3 <= N <= 5,000
N-1 <= M <= 10,000

[Sub-Task Info]
#1 : N <= 10
#2 : N <= 100
#3 : N <= 1,000
#4 : 추가제한조건 없음

Output

병원균의 위크포인트를 모두 제거하여 병원균을 분할하는데 드는 최소비용을 출력한다.

IO Example

입력
9 10
1 2
1 3
2 4
3 4
2 5
5 6
5 7
7 8
7 9
8 9

출력
16



Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]