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

}

巴特西

洛谷 P2872 【[USACO07DEC]道路建设Building Roads】

P2872

首先

那我就说一下kruskal吧.

一、基本思路

二、代码

此题代码及思路：

最新文章

热门文章