8.22--练习赛A题--Building Roads （最小生成树）

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;
}