首页 > 编程语言 >C++ 最小生成树 洛谷

C++ 最小生成树 洛谷

时间：2024-08-03 15:53:48浏览次数：21  
标签：acc va 洛谷 int 最小 C++ 道路 define

介绍：

最小生成树是个啥？其实就像杨志一行人押送生辰纲。抛开最后生辰纲被抢的结局不谈，杨志他们需要到好几个地方，每个地方都需要花点过路费给梁山好汉们打点。比如下面就是一张城市地图：

地图

其中每两个图之间的路径长就是要给梁山好汉们打点的银子数。比如1号地点到2号地点的梁山好汉需要2两银子。那么问题来了，怎样才能选择其中一部分道路就可以到达所有地点且让总花费值最小呢？？？

如果有n个节点（城市），那就至少要连（n-1）条边（路线），并且肯定没有回路。（不信？画几个图试试）众所周知，在无向图中，只要这个图里没有回路（有（n-1）条边），那它就无疑是棵树了。（还是不信？画图......）所以，**我们就管这棵各边权值（费用）和叫“最小生成树”**了。

那这个最小生成树到底怎么搞呢？我们伟大的先哲发明了两种算法：一种叫Kruskal算法，另一种叫Prim算法。我们这里就来介绍一下名字字典序靠前的那个Kruskal吧！（我才不会告诉你根本原因是本蒟蒻不会用Prim呢！）

那咱就开始吧！首先，我们读入的数据是这样的！

1 2 2
1 3 2
1 4 4
2 3 3
3 4 4

其中每一行的a,b,c 3个数是指a到b的路径权值是c哦！

既然题目中让我们求“最小”生成树，那咱们就自然而然地想到先把这些边排个序，先用最小的边，从小到大一路把这棵树搞出来！

说干就干，排一个呗！

1 2 2
1 3 2 
2 3 3
1 4 4
3 4 4

排好之后，映入我们眼帘的是“1，2，2”这条边，二话不说，把它放到生成树里！

过程1

接下来是“1，2，2”，很好，把它也加进去

然后是“2，3，3”，好多同学把它都加了进去......

等会等会，先别忙着加！好像有什么猫腻！前面说过，最小生成树，是不能带回路的，加进去一不是最小，二它连个树都不是，所以不能加！于是我们意识到：在每次加进去新边之前，一定要看看它和其它边会不会构成回路才行！

那咱就只能退而求其次，选其它的边啦，“1，4，4”这可不是回路，没问题！

至此，边数已达（n-1）条，所有点已经选上，最小生成树大功告成！（当然，选下面的“3，4，4”也是阔以的）

总结一下，我们刚才是怎样搞出这棵最小生成树的：

  1. 把边们从小到大排个序
  2. 如果没有回路，一条一条往里加
  3. 边数达到（n-1）条，完成

步骤都弄懂啦！但是这个“回路”到底怎么判断呢？

所谓判断回路，就是看看有了这条边之后，有没有连通的部分，从“树”的角度来看，就是两个点的根节点（也就是“祖宗”）是不是一样的

哎？话说说到这里，诸位有没有联想到什么啊？

没错，就是金光闪闪的并！查！集！

并查集是啥就不在我的责任范围之内啦，（其实就是懒癌犯了）这里我就默认泥萌都会并查集了......

所以说我们可以搞个并查集出来，然后每加入条边时，先用并查集的“查询”功能，看看两个节点的祖宗是不是一样的，如果不一样就把他俩“合并”，就可以放心大胆的往里加啦~

P3366 【模板】最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。

接下来 M 行每行包含三个整数 Xi,Yi,Zi​，表示有一条长度为 Zi​ 的无向边连接结点 Xi,Yi​。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int >
#define fi first
#define se second
#define pb push_back
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;

const int N = 1e6+10;

int n,m;
int acc[N];

pair<int,pair<int,int>> va[N];

int find(int x)
{
	if(acc[x]!=x) acc[x] = find(acc[x]);
	return acc[x];
}

void krukal()
{
	int cnt = 0,sum = 0;
	for(int i = 1;i<=n;i++) acc[i] = i;
	for(int i = 1;i<=m;i++)
	{
		int a = va[i].se.fi,b = va[i].se.se,c = va[i].fi;
		int t1 = find(a),t2 = find(b);
		if(t1!=t2)
		{
			acc[t1] = t2;
			sum += c;
			cnt++;
		}
	}
	if(cnt==n-1) cout<<sum;
	else cout<<"orz";
}

signed main()
{
	IOS;
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		va[i] = {c,{a,b}};
	}
	sort(va+1,va+1+m);
	krukal();
	return 0;
}

P2330 [SCOI2005] 繁忙的都市

题目描述

城市 C 是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市 C 的道路是这样分布的：城市中有 nn 个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：

  1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
  2. 在满足要求 1 的情况下，改造的道路尽量少。
  3. 在满足要求 1、2 的情况下，改造的那些道路中分值最大的道路分值尽量小。

任务：作为市规划局的你，应当作出最佳的决策，选择哪些道路应当被修建。

输入格式

第一行有两个整数 n,m 表示城市有 n 个交叉路口，m 条道路。

接下来 m 行是对每条道路的描述，u,v,c 表示交叉路口 u 和 v 之间有道路相连，分值为 c。

输出格式

两个整数 s,max，表示你选出了几条道路，分值最大的那条道路的分值是多少。

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int >
#define fi first
#define se second
#define pb push_back
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;

const int N = 1e6+10;

int n,m;
int acc[N];

pair<int,pair<int,int>> va[N];

int find(int x)
{
	if(acc[x]!=x) acc[x] = find(acc[x]);
	return acc[x];
}

void krukal()
{
	int cnt = 0,sum = 0;
	for(int i = 1;i<=n;i++) acc[i] = i;
	for(int i = 1;i<=m;i++)
	{
		int a = va[i].se.fi,b = va[i].se.se,c = va[i].fi;
		int t1 = find(a),t2 = find(b);
		if(t1!=t2)
		{
			acc[t1] = t2;
			cnt++;
		}
		if(cnt==n-1) 
		{
			cout<<cnt<<" "<<c;
			break;
		}
	}
	
}

signed main()
{
	IOS;
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		va[i] = {c,{a,b}};
	}
	sort(va+1,va+1+m);
	krukal();
	return 0;
}

P1195 口袋的天空

题目背景

小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。

题目描述

给你云朵的个数 N，再给你 M 个关系，表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成 K 个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。

输入格式

第一行有三个数 N,M,K。

接下来 MM 行每行三个数 X,Y,L，表示 X 云和 Y 云可以通过 L 的代价连在一起。

输出格式

对每组数据输出一行，仅有一个整数，表示最小的代价。

如果怎么连都连不出 K 个棉花糖，请输出 No Answer。

题解：

首先让我们选k朵云做棉花糖，换句话说就是选k个节点构造最小生成树，那不好办！我们都知道，全部n个点的最小生成树有（n-1）条边，那选k个节点就是（n-k）条边呗！

其次就是这个“No Answer”怎么弄的问题，其实也so easy，你想啊，一共就m条边，如果都选完了还没有选出（n-k）条边来，那就是妥妥的No Answer 了

说了这么多，是时候放代码了！听我这么一讲解，大家应该都理解最小生成树的Kruskal算法了吧！

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int >
#define fi first
#define se second
#define pb push_back
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;

const int N = 1e5+10;

int n,m,k;
int acc[N];

pair<int,pair<int,int>> va[N];

int find(int x)
{
	if(acc[x]!=x) acc[x] = find(acc[x]);
	return acc[x];
}

void krukal()
{
	int cnt = 0,sum = 0;
	for(int i = 1;i<=n;i++) acc[i] = i;
	for(int i = 1;i<=m;i++)
	{
		int a = va[i].se.fi,b = va[i].se.se,c = va[i].fi;
		int t1 = find(a),t2 = find(b);
		if(t1!=t2)
		{
			acc[t1] = t2;
			cnt++;
			sum += c;
		}
		if(cnt==n-k) break;
	}
	if(cnt==n-k) cout<<sum;
	else cout<<"No Answer";
}

signed main()
{
	IOS;
	cin>>n>>m>>k;
	for(int i = 1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		va[i] = {c,{a,b}};
	}
	sort(va+1,va+1+m);
	krukal();
	return 0;
}

P1547 [USACO05MAR] Out of Hay S

题目描述

Bessie 计划调查 NN（2≤N≤2 000）个农场的干草情况，它从 1 号农场出发。农场之间总共有 M（1≤M≤104）条双向道路，所有道路的总长度不超过 109。有些农场之间存在着多条道路，所有的农场之间都是连通的。

Bessie 希望计算出该图中最小生成树中的最长边的长度。

输入格式

第一行两个整数 N,M。

接下来 M 行，每行三个用空格隔开的整数 Ai,Bi,Li，表示 Ai,Bi 之间有一条道路，长度为 Li​。

输出格式

一个整数，表示最小生成树中的最长边的长度。

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int >
#define fi first
#define se second
#define pb push_back
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;

const int N = 1e6+10;

int n,m;
int acc[N];

pair<int,pair<int,int>> va[N];

int find(int x)
{
	if(acc[x]!=x) acc[x] = find(acc[x]);
	return acc[x];
}

void krukal()
{
	int cnt = 0,sum = 0;
	for(int i = 1;i<=n;i++) acc[i] = i;
	for(int i = 1;i<=m;i++)
	{
		int a = va[i].se.fi,b = va[i].se.se,c = va[i].fi;
		int t1 = find(a),t2 = find(b);
		if(t1!=t2)
		{
			acc[t1] = t2;
			cnt++;
			sum += c;
		}
		if(cnt==n-1) 
		{
			cout<<c;
			break;
		}
	}
}

signed main()
{
	IOS;
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		va[i] = {c,{a,b}};
	}
	sort(va+1,va+1+m);
	krukal();
	return 0;
}

标签：acc,va,洛谷,int,最小,C++,道路,define
From： https://blog.csdn.net/2401_86043888/article/details/140891578

相关文章

  • 一天速通顺序结构（0基础，软件“Dev-c++”需自己下载）
    今天浅浅带大家速通顺序结构，话不多说，上干货！1，cout语句我们都知道，任何程序都会用到输出，那该怎么实现输出呢，代码实现：#include<iostream>usingnamespacestd;intmain(){cout<<"字符串"；cout<<endl;return0;}其中"#include<iostream>"是头文件，起到声明输入输出......
  • C++动态规划(01背包)
    例题1：有 N 个物品，从 1 到 N 编号。对于每个 i（1≤i≤N），物品 i 的重量是 wi​ 价值是 vi​。太郎决定从 N 个物品里选一些放进背包带回家。太郎的背包的容量是 W，因此放进背包的物品的总重量不能超过 W。求太郎带回家的物品的总价值可能达到的最大值。1.贪......
  • 使用C++实现GB28181信令服务中心
    一。背景：   参照开源的GB28181信令服务wvp，准备使用C++实现一套自研的轻量级GB信令服务中心。因此对GB28181协议进行了梳理并且编写了Demo验证，现在把过程整理下来。   希望将来能够实现一套完整的GB28181信令服务。使用了eXosip库。二。GB28181协议栈：三。GB28181信......
  • 洛谷P6786
    题目原题链接https://www.luogu.com.cn/problem/P6786题目描述小A有一个长度为n的序列a_1,a_2,...,a_n。他想从这些数中选出一些数b_1,b_2,...,b_k满足：对于所有i(1<=i<=k)，b_i要么是序列b中的最大值，要么存在一个位置j使得b_j>b_i且b_i+b_j+g......
  • c++中的标准库
    前言hello，我是文宇。正文C++标准库是C++编程语言的基本组成部分之一，它为开发人员提供了一套丰富和强大的工具和功能，以便快速开发高效、可靠和可移植的应用程序。C++标准库由两个主要部分组成：STL（StandardTemplateLibrary）和非STL部分。STL（标准模板库）是C++标准库的核心部分，......
  • 速通c++（周六）
    前言hello大家好，我是文宇。今天是速通c++的最后一天。（周日是愉快的玩耍，学个毛线）今天是一些用循环写的骚操作（娱乐）正文以下是一些在C++中使用循环进行的有趣和骚操作的例子：打印三角形：intn=5;for(inti=0;i<n;i++){for(intj=0;j<=i;j++){cout......
  • 洛谷P4554 小明的游戏
    小明的游戏题目描述小明最近喜欢玩一个游戏。给定一个n×m的棋盘，上面有两种格子#和@。游戏的规则很简单：给定一个起始位置和一个目标位置，小明每一步能向上，下，左，右四个方向移动一格。如果移动到同一类型的格子，则费用是0，否则费用是1。请编程计算从起始位置移动到目标位置的最小......
  • 最小圆覆盖
    性质一：最小圆覆盖是唯一的证：若存在两个最小圆，如下显然所有点只能存在于两个圆的交集中，于是以中间那条实心蓝线为直径做一个圆，这个圆显然更小而且能够覆盖所有点性质二：若我们已经用最小覆盖圆覆盖了所有点，设这些点的点集为\(S\)，现在我们新加入一个点\(p\)，若\(p\)不在\(S\)的最......
  • 基础算法：离散化(C++实现)
    文章目录1.离散化的定义2.离散化例题2.1离散化+二分2.2离散化+哈希表1.离散化的定义离散化是一种在程序设计和算法优化中常用的技术，其核心思想是将无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。具体来说，离散化是在不改变数据相对大小的条......
  • C++学习笔记之指针高阶
    数组名数组名字是数组的首元素地址。一个指针变量保存了数组元素的地址。我们就称之为数组元素指针，及数组指针。数组指针的本质是指针，指向数组中的某个元素的地址。 由于数组名可以代表数组收元素地址，数组元素是可以通过 数组名[下标]的格式访问，那么可以定义一个指针......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99