本文主要是介绍8.22--练习赛A题--Building Roads （最小生成树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题：
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.
* 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.
* 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.
4 1 1 1 3 1 2 3 4 3 1 4
4.00
题目链接：https://cn.vjudge.net/problem/POJ-3625
题意：有n个村子，有m条路已经修好了。接下来n个坐标，表示村庄。接下来m行表示第i个和第j个村子已经联通了。求村庄互相连通需要的最短的道路。
思路：最小生成树问题，prim算法。注意m个已经联通的路的处理。
源代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <iomanip>
#define MAX 1005
using namespace std;
struct Point
{int x,y;
}point[MAX];
double map[MAX][MAX];
bool visit[MAX];
double dis[MAX];
int m,n;
double s(int i,int j)
{double s1 = point[i].x - point[j].x;double s2 = point[i].y - point[j].y;return (s1 * s1) + (s2 * s2);
}
int main()
{while (scanf("%d%d",&n,&m)!=EOF){//scanf("%d%d",&n,&m);memset(map,0,sizeof(map));for (int i = 1; i <= n; i++)scanf("%d%d",&point[i].x,&point[i].y);for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++)map[i][j] = map[j][i] = double(sqrt(s(i,j)));//这里的距离要注意int a,b;for (int i = 1; i <= m; i++)//已经修好的路距离设为0{scanf("%d%d",&a,&b);map[a][b] = map[b][a] = 0;}memset(visit,0,sizeof(visit));for (int i = 1; i <= n; i++)dis[i] = map[1][i];double sum = 0;visit[1] = 1;dis[1] = 0;int flag = 1;for (int i = 1; i < n; i++){flag = 1;double MIN = 999999999;for (int j = 1; j <= n; j++){if (visit[j] != 1 && dis[j] < MIN){MIN = dis[j];flag = j;}}visit[flag] = 1;sum += MIN;for (int j = 1; j <= n; j++){if (dis[j] > map[flag][j] && visit[j] != 1)dis[j] = map[flag][j];}}cout << setiosflags(ios::fixed) << setprecision(2) << sum << endl;}return 0;
}心得：这个题wa了好几发。。。坑在了求距离上。刚开始直接写的。下次注意用函数写吧还是。。。
这篇关于8.22--练习赛A题--Building Roads （最小生成树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
