P2872
首先
题目概括：题目让着求使所有牧场都联通.需要修建多长的路.
显然这是一道最小生成树板子题（推荐初学者做）.
那我就说一下kruskal吧.
Kruskal算法是一种用来查找最小生成树的算法，由Joseph Kruskal在1956年发表。
用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪心算法的应用。
和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。------- 来自于百度百科
一、基本思路
kruskal利用了一种贪心的思想，先把每一条边按照边权排一下序，利用并查集维护每一个点.
跑kruskal的时候先判断两个点是不是在一个集合里边，如果在那就说明不用再去连边了.
然后合并的时候记录边权，在搞一个记录加的边数的计数器.
大家都知道一张图如果有\(n\)个节点，那么最少\(n-1\)条边就可以吧这张图搞联通了.
那么我们就可以等到计数器的计数记到\(n-1\) 的时候停止执行（已经得到正解）.
然后因为这\(n-1\)条边把图连成一起,那么显然\(n - m\)条边就可以把图分成m个部分（很好想鸭）.例题：P1195
二、代码
for (int i = 1; i <= cnt; i++) {
if (father(edge[i].x) != father(edge[i].y)) {//判断是不是在一个集合中
f++;
unionn(edge[i].x, edge[i].y);//合并
ans += edge[i].dis;//记录总权值
}
if (f == m) break;//如果做完了，那就停下啊.
}
此题代码及思路：
因为有一些边是一开始就有的，那么我们可以吧一开始就有的那些边都赋值成0，然后继续跑kruskal就好了.
因为给出的是坐标，那就先把坐标都存起来，然后把这些坐标依照欧几里得距离两两建边.
欧几里得距离公式：\(\sqrt{((x_{1}-x_{2})*(x_{1}-x_{2}) + (y_{1}-y_{2}) * (y_{1}-y_{2}))}\)
#include <bits/stdc++.h>
#define N 1000010
#define M 2010
using namespace std;
int fath[M], n, m; bool b[M];
double px[M], py[M];
struct node {//结构体存边.
int x, y;
double dis;
}edge[N << 2];
int read() {
int s = 0, f = 0; char ch = getchar();
while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
int father(int x) {
if (x != fath[x]) fath[x] = father(fath[x]);//求是不是在一个集合里
return fath[x];
}
void unionn(int x, int y) {
int fx = father(x), fy = father(y);//合并两个集合
fath[x] = fath[y];
}
bool cmp(node p, node q) {
return p.dis < q.dis;//sort用品
}
int main() {
n = read(), m = read();
int z = n + m;//原本就有的
for (int i = 1; i <= z; i++) fath[i] = i;
int cnt = 0;
for (int i = 1, x, y; i <= n; i++) {
x = read(), y = read();
px[i] = x, px[i] = y;//因为给出的是坐标，先把坐标存起来.
}
for (int i = 1; i <= n; i++) fath[i] = 1;
for (int i = n + 1, x, y; i <= n + m; i++) {
x = read(), y = read();
px[i] = x, py[i] = y;
}
for (int i = 1; i <= n + m; i++) {
for (int j = i + 1; j <= n + m; j++) {//开始存边
cnt++;
edge[cnt].x = i;
edge[cnt].y = j;
edge[cnt].dis = sqrt((px[i] - px[j]) * (px[i] - px[j]) + (py[i] - py[j]) * (py[i] - py[j]));
}
}
sort(edge + 1, edge + cnt + 1, cmp);//给边排一下序
int f = 0;
double ans = 0;
for (int i = 1; i <= cnt; i++) {//kruskal
if (father(edge[i].x) != father(edge[i].y)) {
f++;
unionn(edge[i].x, edge[i].y);
ans += edge[i].dis;
}
if (f == m) break;
}
printf("%.2lf", ans);
}