题意：给坐标系上的一些点，其中有两个点已经连了一条边，求最小生成树的值
将已连接的两点权值置为0，这样一定能加入最小生成树里
最后的结果加上这两点的距离即为所求
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
const int INF=0x3f3f3f3f;
const double eps=1e-;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
int n,m,tt;
const int MAXN=;//最大点数
const int MAXM=;//最大边数
int F[MAXN];//并查集使用
struct Edge
{
int u,v;
double w;
}edge[MAXM];//存储边的信息，包括起点/终点/权值
int tol;//边数，加边前赋值为0
void addedge(int u,int v,double w)
{
edge[tol].u=u;
edge[tol].v=v;
edge[tol++].w=w;
}
bool cmp(Edge a,Edge b)
{//排序函数，讲边按照权值从小到大排序
return a.w<b.w;
}
int find(int x)
{
if(F[x]==-)return x;
else return F[x]=find(F[x]);
}
double Kruskal(int n)//传入点数，返回最小生成树的权值，如果不连通返回-1
{
memset(F,-,sizeof(F));
sort(edge,edge+tol,cmp);
int cnt=;//计算加入的边数
double ans=;
for(int i=;i<tol;i++)
{
int u=edge[i].u;
int v=edge[i].v;
double w=edge[i].w;
int t1=find(u);
int t2=find(v);
if(t1!=t2)
{
ans+=w;
F[t1]=t2;
cnt++;
}
if(cnt==n-)break;
}
if(cnt<n-)return -;//不连通
else return ans;
}
struct node
{
double x,y;
void in()
{
scanf("%lf%lf",&x,&y);
}
}nn[MAXN];
double dist(node a,node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
while(scanf("%d",&n)!=EOF)
{
tol=;
if(n==) break;
int q,p;
scanf("%d%d",&p,&q);
p--,q--;
for(i=;i<n;i++)
{
nn[i].in();
}
for(i=;i<n;i++)
{
for(j=i+;j<n;j++)
{
addedge(i,j,dist(nn[i],nn[j]));
if((i==p&&j==q)||(i==q&&j==p))
{
addedge(i,j,);
}
}
}
printf("%.2lf\n",Kruskal(n)+dist(nn[p],nn[q]));
}
}