코딩을 너무 안 하는것 같아서 가끔 Codeforces를 풀고있는데, 오랜만에 좋은 문제를 찾았다.


문제를 설명하면 간단하게 N개의 정점과 M개의 가중치를 갖는 무향 간선으로 이루어진 그래프가 주어졌을 때, 모든 정점이 연결돼있도록 N-1개의 간선만 남기되(즉, 스패닝 트리를 만들면 된다), 간선의 가중치의 합이 최소가 되도록 하는 방법을 출력하는 것이다. 여기서 각 간선에는 Wi라는 가중치와 Ci라는 속성이 있는데, 가중치를 원하는 만큼 줄일 수 있지만(0이나 음수로도 줄일 수 있다), 1씩 줄일 때마다 Ci의 비용이 소요되고, 지불할 수 있는 자금의 한계 S가 주어진다.


Link: http://codeforces.com/contest/733/problem/F