시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1149 | 700 | 569 | 62.118% |
멀티 컴퓨터 시스템은 여러 개의 노드로 이루어져 있고, 각 노드는 자체 메모리를 가지고 있다. 시스템 상의 각 노드는 단방향 커뮤니케이션 링크로 서로 연결되어 있다. 시스템의 상호 접속 네트워크는 방향 그래프로 나타낼 수 있다. 정점은 노드를 나타내며, 간선은 네트워크의 단방향 링크를 나타낸다. 그림 1은 14개의 노드가 19개의 단방향 링크로 서로 연결된 상호 접속 네트워크를 나타낸다.
선형 배열과 링은 상호 접속 네트워크에서 가장 중요한 두 구조이다. 선형 배열에서 각 양 끝 노드를 제외한 모든 노드는 인접한 노드를 두 개 가진다. 한 노드는 왼쪽, 다른 노드는 오른쪽에 있으며, 두 노드는 모두 공통된 이웃을 통해 연결되어 있다. 이 구조에서 양 끝 점이 연결되었을 때, 그 구조를 링이라고 한다. 즉, 0번부터 k-1번까지, k개 노드로 이루어진 선형 배열은 모든 0 ≤ i < k-1에 대해서 노드 i에서 노드 i+1로 단방향 링크가 존재해야 한다. 여기서 노드 k-1과 노드 0을 연결하는 단방향 링크를 추가하면 링이 된다.
병렬 어플리케이션을 지원하려면, 앞에서 설명한 두 구조 중 하나가 필요하다. 따라서, 시스템을 여러 개의 서브 시스템으로 분해해야 한다. 각 서브 시스템은 링 또는 선형 배열이어야 한다. 서브 시스템은 공통된 노드를 공유할 수 없다.
최근에 발표된 한 보고서에 의하면, k개 노드로 이루어진 링의 가치는 k 달러이고, k개의 노드로 이루어진 선형 배열의 가치는 k-1 달러이다. 따라서, 이익을 최대로 하면서, 시스템을 서브 시스템으로 분해하는 연구가 진행중이다.
한 멀티 컴퓨터 시스템의 상호 접속 네트워크가 주어졌을 때, 이 시스템을 링 과/또는 선형 배열로 분해해서 가치를 최대로 하는 프로그램을 작성하시오. 노드를 1개만 가지는 선형 배열도 존재할 수 있다. 이때, 가치는 0 달러이다.
그림 1. 상호 연결 네트워크를 노드 6개로 이루어진 링 (빨간색)과 노드 8개로 이루어진 선형 배열 (초록색) 으로 분해한 그림이다. 이 분해의 총 가치는 13달러이고, 이 값은 가능한 방법중 최댓값이다.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 상호 네트워크를 이루는 노드의 수 n과 단방향 링크의 수 m이 주어진다. (n ≤ 1,000, m ≤ 50,000) 노드는 0번부터 n-1번까지 번호가 매겨져 있다. 다음 m개 줄에는 u에서 v로 향하는 단방향 링크를 나타내는 두 정수 u와 v가 주어진다. 두 정수는 한 줄에 주어지며, 항상 공백으로 구분되어져 있다.
각 테스트 케이스 마다, 한 줄을 출력한다. 이 줄에는 정수를 하나 포함해야 하며, 정수는 입력으로 주어진 상호 접속 네트워크를 링 과/또는 선형 배열로 분해했을 때 얻을 수 있는 가치의 최댓값이다.
3 4 3 3 2 1 0 2 3 6 6 0 1 1 2 2 3 3 1 3 4 4 5 14 19 0 1 1 2 2 3 3 4 4 5 5 0 5 4 2 1 2 6 6 7 7 8 8 9 9 1 8 7 7 10 10 11 11 12 12 13 13 8
3 5 13