八中生成树1 [MST](C++)

        好久没有更新了，最近学习压力有点大，而且队里学的东西越来越难变态，所以近期我会试着更新一些难题，至于水题嘛。。。我们训练时就没有水题。。。

八中草坪上有N个水龙头，位于（,）
求将个水龙头连通的最小费用。
任意两个水龙头可以修剪水管，费用为欧几里得距离的平方。
校长只愿意修费用大于等于的水管。

输入

第一行给出，
接下来行给出点的坐标x,y
​​​​​​​
,

输出

输出最小费用，如果无解输出

样例输入：

3 11
0 2
5 0
4 3

 样例输出：

46 

1：这道题用最小生成树解决，

我用的是Kruskal算法：

其思路在于将每条边按边权从小到大排序，

每次取相对小的边，

用并查集判断连接该边会不会形成图

如果会，则跳过该边

如不会，则进行操作

2：要用到欧几里得距离的知识；

二维空间公式：

#include
using namespace std;
const int N=2010;
int n;
int c;
int fa[N];
int cnt=0;
int ans=0;
int x[N],y[N];

struct edge {
	int x,y;
	int val;
}e[N*N];

int Euclidean_Metric(int x_x,int x_y,int y_x,int y_y) {//欧几里得距离 
	return (x_x-y_x)*(x_x-y_x)+(x_y-y_y)*(x_y-y_y);//由题意，无需开根 
}

void put (int a,int b) {//建树 
	cnt++;
	e[cnt].x=a;
	e[cnt].y=b;
	e[cnt].val=Euclidean_Metric(x[a],y[a],x[b],y[b]);
}

int find(int x) {
	if(fa[x]!=x)
	    fa[x]=find(fa[x]);
	return fa[x];
}

void unite(int x,int y) {//将x，y放入同一个集合中 
	int p=fa[x],q=fa[y];
	if(p!=q)
	    fa[q]=p;
}

bool cmp(edge a,edge b) {//按边权排序 
	return a.val