ZOJ 2966 Build The Electric System【最小生成ツリー】
1306 ワード
//2632030 2011-08-18 16:57:56 Accepted 2966 C++ 0 1652 ylwh@Unknown
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define N 501
struct edge
{
int x, y, cost;
}e[N * N / 2];
int root[N];
int find_root(int x)
{
int temp = x;
while(temp != root[temp])
temp = root[temp];
root[x] = temp;
return temp;
}
int cmp(struct edge a, struct edge b)
{
return a.cost < b.cost;
}
int main()
{
int t, n, E, i, j, a, b, x, y, cnt, ans;
scanf("%d", &t);
while(t--)
{
cnt = -1;
ans = 0;
scanf("%d%d", &n, &E);
for(i=0; i<n; i++)
root[i] = i;
for(i=0; i<E; i++)
{
scanf("%d%d%d", &x, &y, &j);
if(j)
{
e[++cnt].x = x;
e[ cnt].y = y;
e[ cnt].cost = j;
}
else
{
a = find_root(x);
b = find_root(y);
if(a > b)
root[a] = b;
else if(a < b)
root[b] = a;
}
}
sort(e, e + cnt + 1, cmp);
for(i=0; i<=cnt; i++)
{
a = find_root(e[i].x);
b = find_root(e[i].y);
if(a != b)
{
ans += e[i].cost;
if(a > b)
root[a] = b;
else
root[b] = a;
}
}
printf("%d
", ans);
}
return 0;
}