通信线路 题解

题目描述

见 通信线路

整体思路

只是一个最小生成树的模板题，数据量也没有很大

第一种方法：kruskal算法

两种实现：边集数组：时间复杂度$O(M log M + M(N + M))$；饼查集 并查集：时间复杂度$O(M log M + kM)$。

第二种方法：Prim算法

时间复杂度：$O(N^2)$（heap优化$O(M long M)$）

读者可以自行实现

代码实现

最小生成树的两个主要算法都可以在讲义中找到，点击这个

本题解采用并查集 + kruskal

好孩子不可以抄代码哦

#include <bits/stdc++.h> // 万能头
using namespace std;
int n; // n是城市数
const int N = 1510,M = 1e4 + 10; // N是最大城市数，M是最大边数
struct Edge // 将边的参数定义到结构体里
{
	int x,y,w; // x起点，y终点，w是权重
}e[M];
bool cmp(Edge &a,Edge &b) // 排序按照权重从小到大
{
	return a.w < b.w;
}
int f[N]; // 并查集数组
void init()
{ // 并查集初始化
	for(int i = 1; i <= N; ++i) f[i] = i;
}
int get(int x)
{ // 递归地查询x属于哪个集
	if(x == f[x]) return x;
	return f[x] = get(f[x]);
}
void merge(int x,int y)
{ // 将两个集合并
	int fx = get(x),fy = get(y);
	if(fx != fy) f[fy] = fx;
}
void kruskal()
{ // kruskal本体
	init(); // 初始化
	int ans = 0;
	for(int i = 1;i <= M;i++)
	{
		int x = e[i].x,y = e[i].y,w = e[i].w; // 每次从边集中取出一个权重较小的
		if(get(x) != get(y)) // 如果这条边的两个顶点不属于同一个集（就是不相连的意思）
		{
			merge(x,y); // 合并，即采用这条边
			ans += w; // 总和记得加哦O(∩_∩)O
		}
	}
	cout << ans << endl; // 输出就好乐，也可以返回ans在主函数里输出
}
int main()
{
	freopen("mcst.in","r",stdin); // 文件输入输出
	freopen("mcst.out","w",stdout);
	cin >> n; // 输入城市数
	int ind = 0;
	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < n;j++)
		{
			int op; // 双重循环读入输入的矩阵（确信
			cin >> op; // 第i+1个顶点到第j+1顶点之间边的权重
			if(op != -1) e[ind].x = i + 1,e[ind].y = j + 1,e[ind].w = op,ind++;
			// 如果两个顶点可以有边相连，就放在边集数组
		}
	}
	sort(e,e+M,cmp); // 用cmp来排序
	kruskal(); // kruskal，启动！
	return 0; // 记得return是美德
}