最优布线问题 描述

学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。

当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。

现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。

输入 第一行为整数n（2≤n≤100），表示计算机的数目。此后的n行，每行n个整数。第x+1行yy列的整数表示直接连接第x台计算机和第y台计算机的费用。

样例是对的，但是只是对了20。

#include <bits/stdc++.h>
using namespace std;
long long n,ans,f[1000010];

long long find(int x){
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}

struct node{
	long long x,y,v;
}a[110];

void t(int x,int y,int i){
	x=find(x),y=find(y);
	if(x==y) return;
	f[y]=x;
	ans+=a[i].v;
}

int main(){
	scanf("%lld",&n);
	for(int i=0;i<=n;i++) f[i]=i;
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].v);
		t(a[i].x,a[i].y,i);
	}
	printf("%d",ans);
	return 0;
}