题目链接：http://poj.org/problem?id=2349
题意是有s个通信工具，p个点，然后给出p个点的坐标，需要把每个点都连起来使其连通，通信工具的作用是使任意两个点的权值为0，问使整个图连通需要最少花费多少。
思路就是我们将每个点设置一个编号，然后使任意两点相连，权值为欧几里得距离，求最小生成树，然后减去最小生成树中大的s条边就行了。交题时交C
AC代码：
代码语言：javascript复制#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstring>
#define maxn 505 * 505
using namespace std;
struct Node{
int x,y;
double w;
}Edge[maxn];
int pre[maxn],num;
double ans[maxn],xx[maxn],yy[maxn];
int T,s,n;
bool cmp(Node a,Node b){
return a.w < b.w;
}
void init(){
for(int i=0;i<505;i ) pre[i] = i;
num = 0;
}
void add(int u,int v,double w){
Edge[num].x = u;
Edge[num].y = v;
Edge[num ].w = w;
}
double dist(double x1,double y1,double x,double y){
return sqrt((x1 - x) * (x1 - x) (y1 - y) * (y1 - y));
}
int Find(int x){
if(x != pre[x]) pre[x] = Find(pre[x]);
return pre[x];
}
double Kruskal(){
int cnt = 0;
sort(Edge, Edge num, cmp);
for(int i=0;i<num;i ){
if(Find(Edge[i].x) != Find(Edge[i].y)){
pre[Find(Edge[i].y)] = Find(Edge[i].x);
ans[cnt ] = Edge[i].w;
}
}
return ans[n - s - 1];
}
int main()
{
scanf("%d",&T);
while(T--){
init();
scanf("%d%d",&s,&n);
for(int i=1;i<=n;i ){
scanf("%lf%lf",&xx[i], &yy[i]);
}
for(int i=1;i<n;i ){
for(int j=i 1;j<=n;j ){
double zz = dist(xx[i], yy[i], xx[j], yy[j]);
add(i, j, zz);
}
}
printf("%.2lfn", Kruskal());
}
return 0;
}
