本文主要是介绍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 (最小生成树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!