题目
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.
思路
将已经连接上的点放进同一个并查集中，再用kruskal生成MST，判断条件由一般kruskal的edgeSelected<n-1调整为到图连通为止。
- 能用double就不用float，否则造成精度丢失
- 放进同一个并查集的时候用
root[find(a)]=find(b)，而不是简单的root[a]=b]，因为不能确保已知的每条边都连两个新的独立顶点
代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1001
#define INF 999999999
//int cost[MAXN][MAXN];typedef struct ms
{
double x, y;
}point;typedef struct ed
{
int u, v;double w;
}edge;point cord[MAXN];
int root[MAXN] = {
0 };
vector<edge> Edges;double compDis(point a, point b)
{
double dx = a.x - b.x;double dy = a.y - b.y;return sqrt(dx * dx + dy * dy);
}bool cmp(edge a, edge b)
{
return a.w < b.w;
}int find(int x)
{
int tmp = x;while (root[tmp] != tmp){
tmp = root[tmp];}int k = x;while (k != tmp){
int j = root[k];root[k] = tmp;k = j;}return tmp;
}void join(int x, int y)
{
int rootx = find(x);int rooty = find(y);if (rootx != rooty){
root[rootx] = rooty;}
}bool isConnect(int root[], int n)
{
int cnt = 0;for (int i = 1; i <= n; i++){
if (root[i] == i){
cnt++;}}if (cnt != 1) return false;return true;
}int main()
{
int n, m; cin >> n >> m;for (int i = 1; i <= n; i++){
double x, y; cin >> x >> y;cord[i] = point{
x,y };}for (int i = 1; i <= n; i++){
root[i] = i;}for (int i = 0; i < m; i++){
int a, b; cin >> a >> b;join(find(a), find(b));}for (int i = 1; i < n; i++){
for (int j = i + 1; j <= n; j++){
double w = compDis(cord[i], cord[j]);Edges.push_back(edge{
i,j,w });}}sort(Edges.begin(), Edges.end(), cmp);int i = 0;double res = 0;while (!isConnect(root,n)){
if (find(Edges[i].u) != find(Edges[i].v)){
// cout << Edges[i].u << ' ' << Edges[i].v << ' ' << Edges[i].w << endl;join(find(Edges[i].u), find(Edges[i].v));res += Edges[i].w;}i++;}cout.setf(ios::fixed);cout << setprecision(2) << res << endl;return 0;
}