首页 > 其他分享 >11-03最小生成树

11-03最小生成树

时间:2023-07-20 21:34:13浏览次数:40  
标签:11 03 cnt node int sum tr 最小 顶点

最小生成树

一、定义

      在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即),而 w(u, v) 代表此边的权重,若存在 T 为 E 的子集且为无循环图,使得联通所有结点的的 w(T) 最小,则此 T 为 G 的最小生成树。 w(t) = $\sum_{(u,v)∈t}$w(u,v)
      最小生成树是最小权值生成树的简称

二、算法Kruskal原理

      假设给出了含有n个顶点的连通图,边有若干条,带有自己的权值。
      1.先构建一个只含有n个顶点,边集为空的子图
      2.按照边权大小进行排序,多数从小到大排序
      3.按顺序依次选取边,判断两端点是否已经同属于一个集合(并查集)一个集合则不选取该边,非一个集合选取该边
      4.直到将所有边选完,合并n-1次即可连通,且因为是排序后从小到大进行的选择,将不会有更优的选择,即可求出最小生成树

三、模板代码实现

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e3 + 10, M = 2e5 + 10;

int n, m, cnt, sum;
int f[N];

struct node {
	int x, y, z;
}tr[M];

bool cmp(node u, node v) {
	return u.z < v.z;
}

void init(int n) {
	for (int i = 1; i <= n; i++)
		f[i] = i;
}

int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}

void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x != y) {
		f[x] = y;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> tr[i].x >> tr[i].y >> tr[i].z;
	}
	sort(tr, tr + m, cmp);
	init(n);
	cnt = n, sum = 0;
	for (int i = 0; i < m; i++) {
		int x = tr[i].x;
		int y = tr[i].y;
		if (find(x) != find(y)) {
			merge(x, y);
			cnt--;
			sum += tr[i].z;
		}
	}
	if (cnt != 1) {
		cout << "orz" << endl;
		return 0;
	}
	cout << sum << endl;
	return 0;
} 

四、相关题

1.P2330 繁忙的都市【普及/提高-】

题意:
      给出n,m,表示有n个交叉路口(顶点),m条道路道路(带权边),以下给出m行,每行u,v,c,表示交叉路口u(顶点u)和交叉路口v(顶点v)之间有道路相连,分值为c,需要使得通过选边,使得任意两个交叉路口(顶点)可以互通,同时分值尽可能少,输出选择了几条路,分值最大的那条道路的分值
思路:
      最小生成树
实现:
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e3 + 10, M = 2e5 + 10;

int n, m, cnt, sum;
int f[N];

struct node {
	int x, y, z;
}tr[M];

bool cmp(node u, node v) {
	return u.z < v.z;
}

void init(int n) {
	for (int i = 1; i <= n; i++)
		f[i] = i;
}

int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}

void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x != y) {
		f[x] = y;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> tr[i].x >> tr[i].y >> tr[i].z;
	}
	sort(tr, tr + m, cmp);
	init(n);
	cnt = n, sum = 0;
	for (int i = 0; i < m; i++) {
		int x = tr[i].x;
		int y = tr[i].y;
		if (find(x) != find(y)) {
			merge(x, y);
			cnt--;
			sum = tr[i].z;
		}
	}
	cout << n - 1 << ' ' << sum << endl;
	return 0;
} 

标签:11,03,cnt,node,int,sum,tr,最小,顶点
From: https://www.cnblogs.com/forleaves/p/17569642.html

相关文章

  • (_mysql_exceptions.OperationalError) (2061, 'RSA Encryption not supported -
    RSA加密与数据库操作的关系在进行数据库操作时,我们有时会遇到类似于“(_mysql_exceptions.OperationalError)(2061,'RSAEncryptionnotsupported'”的错误提示。这个错误提示通常表示我们正在尝试使用RSA加密算法进行数据库操作,但是数据库不支持RSA加密。本文将介绍RSA加密算......
  • No qualifying bean of type 'java.lang.String' available: expected at least 1
    Spring中的依赖注入在Spring框架中,依赖注入是一种设计模式,它允许将对象的依赖关系从代码中解耦,并由框架来负责管理这些依赖关系。通过依赖注入,我们可以更容易地编写可维护和可测试的代码。什么是依赖注入?在传统的编程模型中,对象通常通过创建其他对象的实例来满足其依赖关系。这......
  • No qualifying bean of type 'cn.iocoder.yudao.module.personnel.dal.mysql.cust
    解决"Noqualifyingbeanoftype'cn.iocoder.yudao.module.personnel.dal.mysql.cust"问题的流程为了解决"Noqualifyingbeanoftype'cn.iocoder.yudao.module.personnel.dal.mysql.cust"的问题,我们可以按照以下步骤进行操作:步骤操作1确认问题来源2检查bean的......
  • You don't have either docker-client or docker-client-latest installed. Pleas
    如何安装docker-client或docker-client-latest概述在本文中,我将向您展示如何安装docker-client或docker-client-latest,并解释每一步所需的代码及其用途。无论您是一名刚入行的开发者还是有经验的开发者,这篇文章都将帮助您完成安装过程。准备工作在开始之前,请确保您已经正......
  • AGC032F One Third
    首先先证明几个引理。\(\text{Lemma\#1}\):长度为\(1\)的线段上随机取\(n-1\)个点,将其分成\(n\)段,长度最短段的长度期望为\(\dfrac{1}{n^2}\)。证明:我不知道能不能\(\text{Min-Max}\)容斥,但有更简单的做法。假设最小段长度为\(l_{\min}\),考虑枚举\(x\),计算\(......
  • CF1132G Greedy Subsequences
    简单题。\(i\)向\(i\)后第一个\(j\),\(a_j\)比\(a_i\)大的点连边,不难发现最后形成了一棵森林,并且一个点的父亲\(\text{fa}_i>i\)。题目变成了取\([l,r]\)中的点为起点,向祖先方向走去并且终点编号\(\ler\)的最长链长度。考虑离线,维护从每个点开始的最长链长度\(f_i......
  • CF718E Matvey's Birthday
    不难发现答案\(\le15\),极限的情况大概就是\(aabbcc\cdotsgghh\),此时跳一步和走一步等效。这启示我们固定点\(i\),统计\(d(i,j)=D,j<i\)的\(j\)的个数,拆成\(i-j\le15\)的贡献和\(i-j>15\)的贡献。为了方便,以下称从\(i\)到\(i+1\)或\(i-1\)为「走」,在相同颜色......
  • android.widget.TextView.getLayoutParams()' on a null object reference
    解决“android.widget.TextView.getLayoutParams()'onanullobjectreference”错误介绍在Android开发过程中,我们经常会遇到各种错误和异常。其中之一就是"android.widget.TextView.getLayoutParams()'onanullobjectreference"错误。当我们在操作一个TextView的LayoutPar......
  • AGC034F RNG and XOR
    类似随机游走,令\(f_i\)为第一次操作到\(i\)的期望操作次数,\(p_i\)为每次操作数为\(i\)个概率,显然有:\[f_i=\begin{cases}0&i=0\\1+\sum\limits_{j\;\text{xor}\;k\=\i}p_jf_k&i\neq0\end{cases}\]显然可以高斯消元,不过是\(O(2^{3n})\)的,寄飞。考虑到转移过程中有......
  • CF1603D Artistic Partition
    首先如果\(2^k>n\),答案为\(n\)。否则\(k\le\log_2n\),然后就可以令\(dp_{i,j}\)表示前\(i\)个数分\(j\)段的最小答案。\(dp_{i,j}=\min\limits_{k=1}^{i}\{dp_{k-1,j-1}+c(k,i)\}\)。考虑到:\[\begin{aligned}c(l,r)=&\sum\limits_{i=l}^{r}\sum\limits_{j=l}^......