题目大意：给定n个点的坐标，其中m个点已经连接，问把所有点都连接的最小花费？
思路：并查集–Dijkstra，已经连接的就初始化为一个连通块里，然后再跑一边最小生成树就可以了。
code：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; struct node { int x,y; double w; }a[1000010]; int f[800],x[800],y[800]; int n,m,mt; double ans; bool cmp(node aa,node bb) { return aa.w<bb.w; } int find(int st) { if(f[st] != st) f[st] = find(f[st]); return f[st]; } void add(int i,int j) { mt++; a[mt].x = i; a[mt].y = j; a[mt].w = sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(double)(y[i]-y[j])*(y[i]-y[j])); } void dij() { for(int i=1;i<=mt;i++) { int fx = find(a[i].x); int fy = find(a[i].y); if(fx != fy) { f[fy] =fx; ans += a[i].w; } } } int main() { while(~scanf("%d",&n)) { mt = 0; for(int i=1;i<=n;i++) { f[i] = i; scanf("%d%d",&x[i],&y[i]); for(int j=1;j<i;j++) add(i,j); } int xx,yy; scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",&xx,&yy); int fx = find(xx); int fy = find(yy); if(fx != fy) f[fy] = fx; } sort(a+1,a+1+mt,cmp); ans = 0; dij(); printf("%.2f\n",ans); } return 0; }