首页 > 代码库 > POJ3625 Building Roads
POJ3625 Building Roads
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 10803 | Accepted: 3062 |
Description
Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms.
Each of the N (1 ≤ N ≤ 1,000) farms (conveniently numbered 1..N) is represented by a position (Xi, Yi) on the plane (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000). Given the preexisting M roads (1 ≤ M ≤ 1,000) as pairs of connected farms, help Farmer John determine the smallest length of additional roads he must build to connect all his farms.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Two space-separated integers: Xi and Yi
* Lines N+2..N+M+2: Two space-separated integers: i and j, indicating that there is already a road connecting the farm i and farm j.
Output
* Line 1: Smallest length of additional roads required to connect all farms, printed without rounding to two decimal places. Be sure to calculate distances as 64-bit floating point numbers.
Sample Input
4 11 13 12 34 31 4
Sample Output
4.00
Source
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=1020; 9 int n,m;10 struct point{11 double x,y;12 }p[mxn];13 struct edge{14 int x,y;15 double dis;16 }e[mxn*mxn];17 int cmp(edge a,edge b){18 return a.dis<b.dis;19 }20 double dist(point a,point b){21 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));22 }23 //24 int fa[mxn];25 int find(int x){26 if(fa[x]==x)return x;27 return fa[x]=find(fa[x]);28 }29 int cnt=0;30 double ans=0;31 void kruskal(){32 int now=0;33 for(int i=1;i<=cnt && now<n-1;i++){34 int x=find(e[i].x);35 int y=find(e[i].y);36 if(x!=y){37 ans+=e[i].dis;38 fa[x]=y;now++;39 }40 }41 printf("%.2f\n",ans);42 return;43 }44 int main(){45 scanf("%d%d",&n,&m);46 int i,j;47 for(i=1;i<=n;i++) fa[i]=i;48 for(i=1;i<=n;i++)49 scanf("%lf%lf",&p[i].x,&p[i].y);50 for(i=1;i<n;i++)51 for(j=i+1;j<=n;j++){52 e[++cnt].dis=dist(p[i],p[j]);53 e[cnt].x=i;e[cnt].y=j;54 }55 for(i=1;i<=m;i++){56 cnt++;57 scanf("%d%d",&e[cnt].x,&e[cnt].y);58 e[cnt].dis=0;59 }60 sort(e+1,e+cnt+1,cmp);61 kruskal();62 return 0;63 }
POJ3625 Building Roads