레이팅 미적용농부 존(Farmer John)의 N마리 (4 <= N <= 12, N은 짝수) 소들은 건초로 만든 피복으로 보호되는 전선을 설치하여, 친한 소 쌍끼리 통신하는 원시적인 시스템을 구축했다.
각 소에게는 헛간에 정확히 3마리의 친구가 있으며, 소들은 한 줄로 늘어선 N개의 축사를 하나씩 차지하도록 자리를 잡아야 한다. 길이 L의 전선을 만들려면 정확히 L 단위의 건초가 필요하다. 예를 들어 축사 4와 7의 소가 친구라면, 이들을 연결하는 전선을 만드는 데 3 단위의 건초가 든다.
모든 친구 쌍이 별도의 전선으로 연결되어야 한다고 할 때, 소들이 최적의 순서로 자리를 잡는다면 전선들을 만드는 데 필요한 건초의 최소량을 구하시오.
첫째 줄: 정수 N. FJ의 소들은 편의상 1..N으로 번호가 붙어 있다.
둘째 줄부터 1+N번째 줄까지: 각 줄에 1..N 범위의, 공백으로 구분된 세 정수가 주어진다. i+1번째 줄에는 소 i의 세 친구의 번호가 주어진다. 소 i가 소 j의 친구이면, j도 i의 친구이다.
친한 소 쌍을 모두 연결하는 데 필요한 건초의 최소 총량.
haywire.in · 출력을 쓸 파일 haywire.out6
6 2 5
1 3 4
4 2 6
5 3 2
4 6 1
1 5 317Output details: A best ordering of the cows is 6, 5, 1, 4, 2, 3, which requires only 17 units of hay.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > US Open > Bronze