Kruskal , Prim, Union-find등 여러가지 최소 비용 신장트리를 만드는 이론이면 가능하다.
2012-11-22 아직 UVa에서 확인하지는 못했다.
나는 Kruskal로 접근하였고, 다음 블로거분의 도움을 받았다.
#include <iostream>
#include<algorithm>
using namespace std;
struct Graph
{
int start;
int end;
int dist;
}graph[200000+10];
int parent[200000+10];
int size[200000+10];
bool compare(Graph x, Graph y)
{
if(x.dist < y.dist) return true;
return false;
}
//n이 집합 parent에 어느 집합에 속하나 확인
int findParent(int n)
{
int j;
j = n;
while(parent[j] != j)
j = parent[j];
return j;
}
void merge(int p, int q)
{
if(p<q)
parent[q] = p;
else
parent[p] = q;
}
int main()
{
int x, y;
int total;
while(cin>>x>>y)
{
if( x == 0 && y == 0) break;
total = 0;
for(int i = 0; i<y; i++)
{
cin>>graph[i].start>>graph[i].end>>graph[i].dist;
total += graph[i].dist;
parent[i] = i;
}
//가중치를 정렬
sort(graph, graph+y, compare);
int selected = 0;
int countDist = 0;
int k = 0;
while(selected < x - 1)
{
int p = findParent(graph[k].start);
int q = findParent(graph[k].end);
if(p!=q)
{
merge(p,q);
selected++;
countDist+=graph[k].dist;
}
k++;
}
cout<<total - countDist<<endl;
}
return 0;
}