第三天

引子：昨天我们简单讲了讲最小生成树<Dijkstra,Floyd>算法，今天的课程就开始啦！

今天我们要讲的是：最小生成树

Top1：概念

最小生成树，听起来好像是树呀，为什么会是图论呢？其实，处理最小生成树问题前给出的东西，就是一个图，只不过进行操作后要求变成一个最小生成树罢了。

那什么是最小生成树呢？

我们把这个词语拆开来看。

树，我们都好理解，父亲儿砸祖先啥的如果不知道的话......先百度完树再来看吧，那么我们根据树的特性可以得出一个结论：

最小生成树是没有环的

生成树 ，就是一个点到另一个点的路径是 唯一的 ，（可以通过树的无环性质证明），也就是 一个用N-1条边连接的树，且所有点到其他点的路径唯一

最小代表最终生成树的边权和最小（不知道什么是边权的到博主的Blog里面去看吧）。

这里就有一个问题了：为什么会是N-1条边呢，而不是N-2或者N+1条边？

既然要把N个点用最少数量的边（这里不是上面“最小”的定义）将所有点连接起来，（忽略边权）上过小学的都知道，将两个点连起来是要一条边，三个点要两条边，哪里见过三个点用一条边连起来的？用N条边或N+1条边（即上述例子的三条边或四条边），自然就会浪费边了。

主要还是靠自己动手画图思考。

Top2：算法-Kruskal

概念我们讲完了，进入正题。

其实最小生成树还有个算法叫做Prim，Prim算法和Kruskal算法在于，一个在稀疏图中更快，一个在稠密图中更快。然而，Kruskal在比赛中会更好用。

那讲了这么多，Kruskal到底怎么用呢？

我们都知道了树没有环，那么只需要每次取权值最小的边，只要加入这条边之后不行成环，就可以了。

有点像贪心，但是要判断有没有环。

怎么判断有环没环呢？

——并查集

所以代码就很简答啦！

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 5000 + 10;

struct Line{

	int x, y;

	int dis;

	bool operator < (const Line& next) const {

        return dis > next.dis;

    }

};

priority_queue<Line> line;

int n, m, now;

int fa[MAXN];

int ans;

inline int read(){

    int f = 1, x = 0;

    char c = getchar();

    while (c < '0' || c > '9')

    {

        if (c == '-')

            f = -1;

        c = getchar();

    }

    while (c >= '0' && c <= '9')

    {

        x = x * 10 + c - '0';

        c = getchar();

    }

    return f * x;

}

int find(int x){

	if(fa[x] == x)return x;

	return fa[x] = find(fa[x]);

}

int main(){

	n = read(),m = read();

	for(int i = 1;i <= m; i++){

		int x,y,z;

		x = read(),y = read(),z = read();

		Line tot = {x,y,z};

		line.push(tot);

	}

	for(int i = 1;i <= n; i++){

		fa[i] = i;

	}

	while(!line.empty()){

		Line tot = line.top();

		line.pop();

		int nx = tot.x, ny = tot.y;

		if(find(nx) == find(ny)){

			continue;

		}

		fa[find(nx)] = find(ny);

		ans += tot.dis;

		now++;

		if(now == n - 1){

			printf("%d",ans);

			return 0;

		}

	} 

	puts("orz");

	return 0;

}

巴特西

图论-最小生成树<Kruskal>

第三天

Top1：概念

Top2：算法-Kruskal

至于Prim吗......博主太菜，告辞！

最新文章

热门文章