思路:
基本的最小生成树模板题。
AC代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int node[
110];
int _find(
int x){
int xx = x;
while(node[xx] != xx){
xx = node[xx];
}
int temp;
while(x != xx){
temp = node[x];
node[x] = xx;
x = temp;
}
return xx;
}
bool _merge(
int x,
int y){
int xx = _find(x);
int yy = _find(y);
if(xx != yy){
node[yy] = xx;
return false;
}
else{
return true;
}
}
struct edge{
int from,to,v;
}e[
10000];
bool cmp(
const edge &a,
const edge &b){
return a.v < b.v;
}
int main()
{
int n,m;
while(
scanf(
"%d",&n),n){
int m = n*(n-
1)/
2;
for(
int i =
1;i <=
100;i++){
node[i] = i;
}
for(
int i =
1;i <= m;i++){
scanf(
"%d%d%d",&e[i].from,&e[i].to,&e[i].v);
}
sort(e+
1,e+
1+m,cmp);
long long int ans =
0;
for(
int i =
1;i <= m;i++){
if(_merge(e[i].from,e[i].to) ==
false){
ans += e[i].v;
}
}
printf(
"%I64d\n",ans);
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-1132114.html