Barbera

https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 필요한 배경지식 최소 신장 트리 : Minimum Spanning Tree - 크루스칼(Kruskal) 알고리즘 문제 해결 방법 MST를 활용하여 풀어낼 수 있는 문제입니다. i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j를 그래프의 간선으로 표현하면, 문제의 조건에서 Pi,j = Pj,i 라는 것을 확인할 수 있으므로 N개의 논은 무방향 그래프로 나타낼 수 ..