10397 - Connect the Campus--最短路1AC
#include<cstdlib>#include<iostream>#include<sstream>#include<cstdio>#include<cmath>#include<cstring>#include <algorithm>#include<vector>#include<set>#include<queue>#define LL long long#define inf 0x7fffffff#define E 1e-9#define M 100#define N 751using namespace std;struct point{ int x,y;};struct Node{ int x,y; double len;};Node node[N*N];int n,m;int p[N];point f[N];double ma[N][N];void init(){ for(int i=0; i<N; i++) p[i]=i;}int tou(int x){ if(p[x]!=x) p[x]=tou(p[x]); return p[x];}double length(point p1,point p2){ return sqrt((p1.y-p2.y)*(p1.y-p2.y)+(p1.x-p2.x)*(p1.x-p2.x));}bool cmp(Node a,Node b){ return a.len<b.len;}int main(){#ifndef ONLINE_JUDGE freopen("ex.in","r",stdin);#endif while(scanf("%d",&n)!=EOF) { int x,y; memset(ma,0,sizeof(ma)); init(); for (int i=0; i<n; i++) scanf("%d%d",&f[i].x,&f[i].y); scanf("%d",&m); int fax,fay; for (int i=0; i<m; i++) { scanf("%d%d",&x,&y); x--,y--; ma[x][y]=ma[y][x]=-1; fax=tou(x); fay=tou(y); if(fay!=fax) p[fax]=fay; } int cnt=0; for(int i=0; i<n; i++) for(int j=i+1; j<n; j++) if(ma[i][j]!=-1) { node[cnt].len=length(f[i],f[j]); node[cnt].x=i; node[cnt].y=j; cnt++; } sort(node,node+cnt,cmp);// for(int i=0;i<cnt;i++)// cout<<node[i].x<<" "<<node[i].y<<" "<<node[i].len<<endl; double ans=0.0; for(int i=0; i<cnt; i++) { fax=tou(node[i].x); fay=tou(node[i].y); if(fax!=fay) { p[fax]=fay; ans+=node[i].len; } } printf("%.2lf\n",ans); } return 0;}