题目：
输入输出样例
input:
4 1
1 1
3 1
2 3
4 3
1 4
output:
4.00
思路：
连通问题考虑最小生成树
法一：
prim算法（参考模板），原模板是将lowcost[i]=0认为是用过的点，所以我们将已经连起来的边的距离设为-1以示区别。我一开始的想法是将每个边都加到ans里，然后补一个m就行，但是题目中所给的边可能会成环（即不是每条边都可以用到），所以需要一个cnt来记录ans里加了多少个-1。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#define maxn 1111
using namespace std;
int n,m,x,y;
int cnt=0;
double ans=0;
double a[maxn][maxn],lowcost[maxn],adjvex[maxn];
struct farms
{
double x,y;
}f[maxn];
int main()
{
cin>>n>>m;for(int i=1;i<=n;i++) a[i][i]=0;for(int i=1;i<=n;i++) cin>>f[i].x>>f[i].y;//for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=1e18;for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
double temp=sqrt((f[i].x-f[j].x)*(f[i].x-f[j].x)+(f[i].y-f[j].y)*(f[i].y-f[j].y));a[i][j]=temp;a[j][i]=temp;//cout<<"i="<<i<<" "<<"j="<<j<<"temp="<<temp<<" "<<a[i][j]<<endl;}}for(int i=1;i<=m;i++){
cin>>x>>y;a[x][y]=-1;a[y][x]=-1;}/*for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<"i="<<i<<" "<<"j="<<j<<"a[i][j]"<<a[i][j]<<endl;}}*/for(int i=1;i<=n;i++) lowcost[i]=1e18;for(int i=1;i<=n;i++){
if(a[1][i]){
lowcost[i]=a[1][i];adjvex[i]=1;} }lowcost[1]=0;//表示1已经用过了/*for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<"i="<<i<<" "<<"j="<<j<<"a[i][j]"<<a[i][j]<<endl;}}*/for(int i=1;i<=n;i++){
double minn=1e18;int temp=0;//for(int j=1;j<=n;j++) cout<<lowcost[j]<<" ";//cout<<endl;for(int j=1;j<=n;j++){
if(lowcost[j]!=0&&lowcost[j]<minn){
temp=j;minn=lowcost[j];//找到相连的最小权值的点//cout<<"min="<<minn<<endl;}}if(minn==-1) cnt++;ans+=minn; //cout<<"ans="<<ans<<endl;lowcost[temp]=0;for(int j=1;j<=n;j++){
if(a[temp][j]!=0&&a[temp][j]<lowcost[j]&&lowcost[j]!=0){
lowcost[j]=a[temp][j];adjvex[j]=temp;}}int flag=1;for(int i=1;i<=n;i++){
if(lowcost[i]) flag=0;}if(flag) break;}/*int flag=0;for(int i=1;i<=n;i++){if(lowcost[i]) flag=1;}//判断是否联通if(flag) cout<<"orz"<<endl;else */ ans+=cnt;printf("%.2f",ans);return 0;
}
法二：
依旧是prim算法，但是模板改了一点，另外用了一个数组来记录是否联通。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#define maxn 1111
using namespace std;
int n,m,x,y;
double ans=0;
double a[maxn][maxn],lowcost[maxn];
bool visited[maxn];
struct farms
{
double x,y;
}f[maxn];
int main()
{
cin>>n>>m;for(int i=1;i<=n;i++) a[i][i]=0;for(int i=1;i<=n;i++) cin>>f[i].x>>f[i].y;//for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=1e18;for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
double temp=sqrt((f[i].x-f[j].x)*(f[i].x-f[j].x)+(f[i].y-f[j].y)*(f[i].y-f[j].y));a[i][j]=temp;a[j][i]=temp;//cout<<"i="<<i<<" "<<"j="<<j<<"temp="<<temp<<" "<<a[i][j]<<endl;}}for(int i=1;i<=m;i++){
cin>>x>>y;a[x][y]=0;a[y][x]=0;}/*for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<a[i][j]<<" ";}cout<<endl;}*/for(int i=0;i<=n;i++) lowcost[i]=1e18;for(int i=1;i<=n;i++) lowcost[i]=a[1][i];lowcost[1]=0;//表示1已经用过了visited[1]=1;for(int i=1;i<=n;i++){
//double minn=1e18;int temp=0;//for(int j=1;j<=n;j++) cout<<lowcost[j]<<" ";//cout<<endl;for(int j=1;j<=n;j++){
if(!visited[j]&&lowcost[j]<lowcost[temp]){
temp=j;//找到相连的最小权值的点//cout<<"min="<<minn<<endl;}} //cout<<"ans="<<ans<<endl;visited[temp]=1;for(int j=1;j<=n;j++){
if(!visited[j]&&a[temp][j]<lowcost[j]){
lowcost[j]=a[temp][j];}}}//for(int i=1;i<=n;i++) cout<<lowcost[i]<<" ";//cout<<endl;for(int i=1;i<=n;i++){
ans+=lowcost[i];}//判断是否联通printf("%.2f",ans);return 0;
}
法三：
一开始我是想用kruskal算法的，但是由于想着分组，后续比较麻烦。所以去用prim算法了，经请教，发现可以直接把现有的边直接连起来，然后对所以的边进行排序，一波暴力。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#define maxn 1111
using namespace std;
int n,m;
int fa[maxn];
struct edge
{
int x,y;double z;bool operator<(const edge &e1)const{
return z<e1.z;}
}e[maxn*maxn];
int getfa(int x)
{
return (x==fa[x])?x:(fa[x]=getfa(fa[x]));
}
void merge(int x,int y)
{
int xx=getfa(x),yy=getfa(y);if (xx==yy) return;fa[xx]=yy;
}
double x[maxn],y[maxn];
int main()
{
cin>>n>>m;for (int i=1;i<=n;i++) cin>>x[i]>>y[i];double ans=0;int cnt=0;for (int i=1;i<=n;i++) fa[i]=i;for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) e[++cnt]={
i,j,sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))};for (int i=1;i<=m;i++){
int x,y;cin>>x>>y;merge(x,y);}sort(e+1,e+cnt+1);for(int i=1;i<=cnt;i++){
if(getfa(e[i].x)!=getfa(e[i].y)){
merge(e[i].x,e[i].y);ans+=e[i].z;}}printf("%.2lf\n",ans);return 0;
}