洛谷 P2212 【[USACO14MAR]Watering the Fields S】

一道最小生成树模板题，这里用的Kruskal算法，把每两点就加一条边，跑一遍最小生成树即可。

#include <bits/stdc++.h>

using namespace std;

struct node{

	int l , r , w;

};

node e[4000010];

int n , maxx , tot , now , ans;

int fa[2010] , a[2010] , b[2010];

int find(int x){

	if(x == fa[x]) return x;

	return fa[x] = find(fa[x]);

}

bool cmp(node x , node y){

	return x.w < y.w;

}

int work(int i , int j){

	return (a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]);

}

int main(){

	cin >> n >> maxx;

	for(int i = 1; i <= n; i++){

		fa[i] = i;

		cin >> a[i] >> b[i];

	}

	for(int i = 1; i <= n; i++)

		for(int j = 1; j < i; j++){	//只用输入一半

			int x = work(i , j);

			if(x < maxx) continue;

			tot++;

			e[tot].l = i;

			e[tot].r = j;

			e[tot].w = x;

		}

	sort(e + 1 , e + tot + 1 , cmp);

	for(int i = 1; i <= tot; i++){

		if(now == n - 1) break;

		int x = find(e[i].l) , y = find(e[i].r);

		if(x == y) continue;

		fa[x] = y;

		now++;

		ans += e[i].w;

	}

	if(now != n - 1) cout << -1;	//边数不够

	else cout << ans;

	return 0;

}