| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 8999 | Accepted: 2596 |
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 1 1 1 3 1 2 3 4 3 1 4
Sample Output
4.00
题意：n个村庄，m条已经修好的道路，接下来n行表示n个村庄的坐标（xi，yi），m行表示两个村庄（a，b）已经修好道路。求n个村庄互相连通需要修建的最短道路。
思路：最小生成树
Prim算法：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#define INF 999999
#define M 1005
using namespace std;
double map[M][M],len[M]; // 注意类型
int vis[M];
int x[M],y[M];
double dis(int i,int j) // 任意两个村庄的距离
{
double k1,k2,k;
k1=x[i]-x[j];
k2=y[i]-y[j];
k=sqrt(k1*k1+k2*k2);
return k;
}
int main ()
{
int n,m,a,b;
int i,j;
int temp;
double sum;
while(cin>>n>>m)
{
memset(map,0,sizeof(map));
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++)
cin>>x[i]>>y[i];
for(i=1;i<=n;i++)
for(j=1;j<n;j++)
map[i][j]=map[j][i]=dis(i,j);
for(i=0;i<m;i++)
{
cin>>a>>b;
map[a][b]=map[b][a]=0; // 巧妙处理。若已经修好道路，则长度赋值为0.
}
for(i=1;i<=n;i++)
len[i]=map[1][i];
vis[1]=1;
sum=0.0;
for(i=1;i<n;i++)
{
double min=INF;
for(j=1;j<=n;j++)
{
if(!vis[j] && len[j]<min)
{
min=len[j];
temp=j;
}
}
sum+=min;
vis[temp]=1;
for(j=1;j<=n;j++)
{
if(!vis[j] && len[j]>map[temp][j])
len[j]=map[temp][j];
}
}
printf("%.2lf\n",sum);
}
return 0;
}
poj 3625 Building Roads,布布扣,bubuko.com
原文：http://blog.csdn.net/fyxz1314/article/details/38024391