시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
8 초 | 256 MB | 1946 | 643 | 373 | 30.649% |
V의 집합과 간선 E의 집합으로 이루어진 양방향 그래프 G = ( V, E )가 주어진다. 이 그래프는 연결 그래프이다. 즉, 모든 정점쌍 간에 적어도 하나 이상의 경로가 존재한다. 각각의 정점들은 검정색 또는 흰색이다. 동전은 정점들 위에 하나씩 놓여 있는데 이 동전도 검정색 또는 흰색이다. 이 그래프에서 '동전 교환' 연산을 통해 인접한 정점 위에 있는 동전 2개의 위치를 서로 맞바꿀 수 있다. 아래 그림을 보면 이해 할 수 있을 것이다. (그림 1에서 네모의 색은 동전의 색깔이다.)
그림 1. '동전 교환' 연산의 예 (2 <> 5, 5 <> 6, 1 <> 5)
우리가 구하고자 하는 것은 모든 검정색 동전을 검정색 정점 위로, 모든 흰색 동전을 흰색 정점 위로 올리기 위해 필요한 '동전 교환' 연산의 최소 횟수이다.
입력의 첫줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫줄에는 정수 n과 m (1 ≤ n ≤ 500, n-1 ≤ m ≤ n(n-1)/2 )이 주어진다. 여기서 n은 정점의 개수, m은 간선의 개수를 나타낸다. 정점은 1 ~ n의 번호를 가진다. n, m의 다음줄부터 m 줄에 걸쳐서 인접한 두 정점 x, y (1 ≤ x < y ≤ n)이 주어진다. 그 다음 줄에는 0 또는 1의 값을 가지는 n개의 정수가 주어진다. 여기서 i (1 ≤ i ≤ n)번째 정수는 정점 i의 색깔이다. 0은 검정색 1은 흰색이다. 그 다음 줄에도 0 또는 1의 값을 가지는 n개의 정수가 주어지고 여기서 i (1 ≤ i ≤ n)번째 정수는 정점 i위에 있는 동전의 색깔을 의미한다.
한 테스트케이스당 한 줄에 걸쳐 모든 동전과 정점의 색깔을 일치시키기 위해 필요한 최소 '동전 교환' 연산의 횟수를 출력하라.
3 4 4 1 2 1 3 2 4 3 4 0 1 1 0 0 1 0 1 6 7 1 2 1 5 1 4 2 3 2 5 4 5 5 6 1 1 0 0 0 0 0 0 0 0 1 1 6 5 1 2 2 3 3 4 4 5 5 6 1 0 1 1 0 0 0 0 1 1 0 1
1 3 5
ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Daejeon 2015 A번