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

最小生成树

时间：2024-02-05 14:48:57浏览次数：16  
标签：sz int 边权 最小 long 生成

【最小生成树是什么】

在一张图 \(G\)（设 \(n\) 个结点）中，选取 \(n-1\) 条边，用这些边把结点之间连通。

那么这 \(n-1\) 条边和原来的结点所构成的图 \(S\)，就叫做 \(G\) 的生成树。

最小生成树，就是希望 \(S\) 中边权的和最小。

而求最小生成树，有两种比较常用的方法：Kruskal 和 Prim 。

（Kruskal 代码更简单，所以更常用）

【Kruskal 算法】

每次选 连接不同连通块的 最小边权的 边。

证明：

反证法，假设不连这条边。

要连接这两个连通块，一定是这两个连通块之间连了其它的边，或者通过其它连通块连起来。

但是这些边的边权一定大于等于这条最小的边。

连上刚才选出来的最小边，为了不形成环，一定要删掉一条这个环上的边。

只要删掉一条大于等于它的边，一定至少更优。

而且，因为删掉之后依然连通，而且边数不变，所以图还是一棵树。

【推论】

对任意边权的边，在任何一种最小生成树方案中，这种边权的边一定用了同一个数量。

证明：

数学归纳法。

假设当比 \(x\) 小的边权都满足上面的推论，下面证明 \(x\) 边权也满足推论。

分类讨论：

  1. \(x\) 的边权选的比最小生成树的少。

设一条少选的边为 \(e\)，\(e\) 起到的作用是连接了 \(u,v\) 两个连通块。

为了连接这两个连通块，之后一定需要若干条长度大于 \(x\) 的边。

  1. \(x\) 的边权选的比最小生成树的多。

按照 Kruskal 算法，最小生成树的选法已经是尽可能多地选边了，不可能选的还要多。

所以推论成立。

【适用场景】

绝大多数求最优生成树的问题，Kruskal 都可以胜任。

而对于那些边与边之间比较独立的问题（比如两个边之间还要满足一些要求，就不独立），Kruskal 非常好用。

因为 Kruskal 只要一开始排个序，然后按照既定流程跑一遍就是最优。

我们只需要思考一下，排序的 \(cmp\) 函数怎么写就行了。

【实现】

判断是否连接不同连通块，用并查集即可。

【Code】

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
struct Edge{
	int x, y, w;
} e[200005];
int p[5005], sz[5005], cnt;

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

int fnd(int x) {
	if (p[x] == x)
		return x;
	return p[x] = fnd(p[x]);
}

void unn(int x, int y) {
	int px = fnd(x), py = fnd(y);
	if (px == py)
		return;
	if (sz[px] > sz[py])
		swap(px, py);
	sz[py] += sz[px], p[px] = py;
}

int main() 
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		cin >> e[i].x >> e[i].y >> e[i].w;
	sort(e + 1, e + m + 1, [](Edge x, Edge y){return x.w < y.w;});
	init();
	int ans = 0, cnt = n;
	for (int i = 1; i <= m; i++)
		if (fnd(e[i].x) != fnd(e[i].y))
			ans += e[i].w, unn(e[i].x, e[i].y), cnt--;
	if (cnt != 1)
		cout << "orz" << endl;
	else
		cout << ans << endl;
	return 0;
}

【Prim】

很像 Dijkstra。

每次考虑把一个点加入进最小生成树中。

\(dis[i]\) 为 \(i\) (V中) 到任意 U 中的点的最小距离。

每次把 \(dis[i]\) 最小的点加入，并更新 \(dis\)。

正确性证明就像 Kruskal，如果不连这条边，一定是通过了现在 V中的点绕了一圈，但是这条边已经是最短的，于是一定不会更优。

【使用场景】

当有一个固定的起点，或者两个边之间不太独立，适合 Prim 。

Prim 的中间结果一定是一个大的连通块，而 Kruskal 可能是几个连通块。

例如滑雪这题就比较适合 Prim。

  1. 有一个固定的起始点 1 号；

  2. 图是有向的，但是按照 Kruskal 可能会把两条相撞的边都选了，但是 Prim 会按照方向一个一个推下去。

注：也可以先按照目标节点高度排序，再按边权排序，然后跑 Kruskal 。

【Code】

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;

long long n, m, u, v, x[1005], y[1005];
double mtr[1005][1005];

//U当中的点已经加入MST，其余的待加入 
double dis[1005];//dis[k]为k到U中点的最小边权 
bool f[1005];//f[k]=true表示k在U当中 
double Prim() {
	double ans = 0;//最终的值 
	for (int i = 1; i <= n; i++)
		dis[i] = 9e18, f[i] = false;
	f[1] = true;//初始，把1加入
	for (int j = 1; j <= n; j++)//初始，所有点到U中为到1的距离 
		dis[j] = mtr[1][j];
	for (int i = 1; i < n; i++) {//依次加入剩余n-1个点到U 
		int pos = -1;//下一个要加入的点 
		for (int j = 1; j <= n; j++)
			if (!f[j] && (pos == -1 || dis[pos] > dis[j]))
				pos = j; 
		//把点pos加入U，相当于连了边权dis[pos]的那条边 
		ans += dis[pos], f[pos] = true; 
		for (int j = 1; j <= n; j++)
			if (!f[j]) 
				dis[j] = min(dis[j], mtr[pos][j]); 
	} 
	return ans;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> x[i] >> y[i];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			mtr[i][j] = mtr[j][i] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
	for (int i = 1; i <= m; i++) {
		cin >> u >> v;
		mtr[u][v] = mtr[v][u] = 0;
	}
	
	printf("%.2lf\n", Prim());
	return 0;
}

【次小生成树】

对任意边权的边，在任何一种最小生成树方案中，这种边权的边一定用了同一个数量。

没达到最小，一定是有一种边权没选够。

注意：一定不是选多了，不然比最小生成树还小了。

枚举所有边权 k，O（m）跑一遍最小生成树检验，当循环到边权 k 的边时，强制少拿一条边，之后接着跑就可以了。 O(nm)

还有第二种方法：

枚举所有没有被选进最小生成树的边，尝试用这种边替换掉原来的边，从两端一路找上去，替换掉比他小的最大的边。

这个想法有一个预设前提：

任何最小生成树，都存在一种次小生成树和他只差一条边。

原理：还是上面那个结论。

次小生成树一定有一个边权的边选的比最小生成树恰好少一条。（如果少两条，后面就要补两条，不如只少一条）

这里已经差了一条，后面除了补的那一条，其它都和最小生成树一样，就是最好的了。

第二种方法还可以用倍增优化。

任意一条没有选的边 \(e\) 从两端一路找上去，一定没有边比 \(e\) 的边权更大，否则用 \(e\) 替换这条边，我们得到一颗更小的生成树，这与我们一开始找出 MST 矛盾。

所以从 \(e\) 的两端走上去，所有边的边权要么等于 \(e\) 的边权，要么小于 \(e\) 的边权。

因此我们可以记录：\(f[u][k]\) 表示 \(u\) 往上走 \(2^k\) 个结点，最大的边权；\(g[u][k]\) 表示往上走次大的边权。（严格次大）

如果 \(f[e.u][...]\) 等于 \(e\) 的边权，则选择 \(g[e.u][...]\) 的边和 \(e\) 替换。（当然，如果是非严格次小生成树，则连 \(g\) 数组都不用记录）

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long n, m;
struct Edge{
	long long x, y, w;
} e[20005];
long long p[2005], sz[2005], cnt;

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

long long fnd(long long x) {
	if (p[x] == x)
		return x;
	return p[x] = fnd(p[x]);
}

void unn(long long x, long long y) {
	long long px = fnd(x), py = fnd(y);
	if (px == py)
		return;
	if (sz[px] > sz[py])
		swap(px, py);
	sz[py] += sz[px], p[px] = py;
}

bool cmp(Edge a, Edge b) {
	return a.w < b.w;
}

vector<Edge> tr, not_tr;

pair<long long, long long> fa[2005] = {};
long long d[2005] = {}; 

vector<Edge> ee[2005];

void dfs(long long u, long long pr, long long dth) {
	fa[u].first = pr;
	d[u] = dth;
	for (int i = 0; i < ee[u].size(); i++)
		if (ee[u][i].y != pr) {
			fa[ee[u][i].y].second = ee[u][i].w;
			dfs(ee[u][i].y, u, dth + 1);
		}
}

//在寻找lca(x,y)的过程中，返回路上的小于w的最大边权 
long long _get(long long x, long long y, long long w) {
//	cout << x << ' ' << y << ' ' << w << ' ' << d[x] << ' ' << d[y] << endl;
	
	if (d[x] < d[y])
		swap(x, y);
	long long mx = -9e18;
	
	while (d[x] > d[y]) {
		
		if (fa[x].second < w)
			mx = max(mx, fa[x].second);
		x = fa[x].first;
	}
	
//	cout << x << ' ' << y << endl;
	
	while (x != y) {
		if (fa[x].second < w)
			mx = max(mx, fa[x].second);
		if (fa[y].second < w)
			mx = max(mx, fa[y].second);
		x = fa[x].first;
		y = fa[y].first;
	}
	
	return mx;
}

long long sum = 0;
long long ans;

int main() 
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		cin >> e[i].x >> e[i].y >> e[i].w;
	sort(e + 1, e + m + 1, cmp);
	init();
	for (int i = 1; i <= m; i++) {
		if (fnd(e[i].x) == fnd(e[i].y)) {
			not_tr.push_back(e[i]);
			continue;
		}
		sum += e[i].w;
		tr.push_back(e[i]);
		unn(e[i].x, e[i].y);
	}
	
	for (int i = 0; i < tr.size(); i++) {
//		cout << tr[i].x << ' ' << tr[i].y << ' ' << tr[i].w << endl;
		ee[tr[i].x].push_back((Edge){tr[i].x, tr[i].y, tr[i].w});
		ee[tr[i].y].push_back((Edge){tr[i].y, tr[i].x, tr[i].w});
	}
	
	dfs(1, 0, 1);
	fa[1].second = 9e18;
	ans = 9e18;
	
	for (int i = 0; i < not_tr.size(); i++) {
		long long w = _get(not_tr[i].x, not_tr[i].y, not_tr[i].w);
		ans = min(ans, sum - w + not_tr[i].w);
	}
	
	cout << ans << endl;
	return 0;
}

【最小生成树计数】

最小生成树计数

上面的结论：对于任意的一棵最小生成树，一个边权的条数是一定的。

先跑一遍最小生成树，求得各个条数。

搜索，搜索每个边权，枚举这条边选还是不选。

但是这就需要回溯，而并查集是 “不能分开” 的。

考虑在每个操作上额外记录操作具体属性，做一个结构体栈，合并时把操作加入栈。

搜索完，用栈顶的操作所记录的属性还原即可。

【题目】

构造完全图

假设我们要用一条边权 \(w\) 的边连接两个连通块。

为了使最小生成树唯一，连接这两个连通块的边一定至少 \(z + 1\)。

于是我们枚举每一条最小生成树的边，对每一条边统计贡献即可。

贡献 = \((sz_x \times sz_y - 1)\times (w + 1)\)。

Tree I

考虑一个技巧：额外边权。

给所有黑边加上一个固定边权，这样在排序里黑边就会靠后，白边就会选更多。

这个边权很明显可以二分，二分出来之后求答案再减去多余边权。

洛谷

繁忙的都市：最大边权最小的生成树。

Out of Hay S：边权最小生成树的最大边。

局域网：总边权和 减去 最小生成树的边权和。

新的开始：建立虚拟 0 号点，0 到每个点的距离就是在那个点建立发电机的距离，然后跑一遍最小生成树。

聪明的猴子：把两点距离公式带进去变成边权。

Tractor S：跑最小生成树，如果中间有一次规模够了，输出边权。

公路修建问题：二分最大边权最小值，二分完再跑一遍求方案。

滑雪：

两种方法：

  1. 类似 Prim 算法，从 1 号点开始，每次扩展能滑到的最近的。

  2. Kruskal 算法的排序规则，把终点高度高的放在前面，因为有矛盾一定是先下后上，所以这样子排序一定不会出矛盾。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5;

int n, m;
int h[N];

int cur = 0;
struct Edge {
	int u, v, w;
} e[M];

bool cmp(Edge a, Edge b) {
	if (h[a.v] != h[b.v])
		return h[a.v] > h[b.v];
	return a.w < b.w; 
}

int p[N], sz[N];
void init() {
	for (int i = 1; i <= n; i++) {
		p[i] = i;
		sz[i] = 1;
	}
}

int fnd(int x) {
	if (p[x] == x)
		return x;
	return p[x] = fnd(p[x]);
}

void unn(int x, int y) {
	x = fnd(x);
	y = fnd(y);
	if (x == y)
		return ;
	if (sz[x] > sz[y])
		swap(x, y);
	p[x] = y;
	sz[y] += sz[x];
}

struct Edge2 {
	int to, val;
};
vector<Edge2> E[N];

int cnt = 0;
bool vis[N] = {};
void dfs(int u) {
	vis[u] = true;
	cnt++;
	for (int i = 0; i < E[u].size(); i++)
		if (!vis[E[u][i].to]) 
			dfs(E[u][i].to);
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> h[i];
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		if (h[u] >= h[v])
			E[u].push_back((Edge2){v, w});
		if (h[v] >= h[u])
			E[v].push_back((Edge2){u, w});
	}
	dfs(1);
	cout << cnt << ' ';
	
	long long ans = 0;
	
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < E[i].size(); j++)
			if (vis[i] && vis[E[i][j].to])
				e[++cur] = (Edge){i, E[i][j].to, E[i][j].val};
	
	sort(e + 1, e + cur + 1, cmp);
	init();
	for (int i = 1; i <= cur; i++) {
		if (fnd(e[i].u) != fnd(e[i].v)) {
			ans += e[i].w;
			unn(e[i].u, e[i].v);
		}
	}
	
	cout << ans << endl;
	return 0; 
}

Cow Neighborhoods G：

正解没想出来，纯暴力拿 93 分。

首先 \(O(n^2)\) 很简单，枚举任意两个点连边就行了。

但是，因为有一些点完全没有必要枚举，所以我们其实 \(O(n^2)\) 有很多浪费。

考虑把点按横坐标从小到大排序，然后对每个点只和它之后 1500 个点连边，加一个 O2 优化跑的飞快。

但是这个方法没办法照顾所有情况，所以还是 WA 一个点。

不过按照横坐标、纵坐标各排序一次，再连边，应该可以 AC。

所以这题和生成树有啥关系？？？

Codeforces

Spanning Tree：纯模板。

Dense Spanning Tree：数据范围小，可以直接枚举最小边权，然后往后加边。如果可行就更新答案。

No refuel：最大边权最小的生成树，其实还是按照从小到大排序。

Oil business：

题目大意：删除尽可能多的边，使整个图连通，但是删去的边的边权之和 \(\leq s\)。

一个简单想法就是所有删去的边的边权都尽可能小，而 Kruskal 按边权从大到小排序恰好可以满足这个条件。

所以跑一遍最大生成树，然后从小到大遍历所有没选上的边，如果加了不会超就加进去。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;
long long s;
struct Edge {
	int u, v, w;
	int id;
} e[100005];
bool us[100005] = {};

bool cmp(Edge a, Edge b) {
	if (a.w != b.w)
		return a.w > b.w;
	return a.id > b.id;
}

int p[100005], sz[100005];
void init() {
	for (int i = 1; i <= n; i++) {
		p[i] = i;
		sz[i] = 1;
	}
}

int fnd(int x) {
	if (x == p[x])
		return x;
	return p[x] = fnd(p[x]);
}

void unn(int x, int y) {
	x = fnd(x);
	y = fnd(y);
	if (x == y)
		return ;
	if (sz[x] > sz[y])
		swap(x, y);
	p[x] = y;
	sz[y] += sz[x];
}

int main() {
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++) {
		cin >> e[i].u >> e[i].v >> e[i].w;
		e[i].id = i;
	}
	sort(e + 1, e + m + 1, cmp);
	init();
	for (int i = 1; i <= m; i++) {
		if (fnd(e[i].u) != fnd(e[i].v)) {
			unn(e[i].u, e[i].v);
			us[e[i].id] = true;
		}
	}
	
	int ans = 0;
	long long sum = 0;
	vector<int> ANS;
	
	for (int i = m; i >= 1; i--) {
		if (!us[e[i].id]) {
			sum += e[i].w;
			if (sum > s)
				break;
			ans++;
			ANS.push_back(e[i].id);
		}
	}
	
	cout << ans << endl;
	sort(ANS.begin(), ANS.end());
	for (auto i: ANS)
		cout << i << ' ';
	return 0;
}

标签：sz,int,边权,最小,long,生成
From： https://www.cnblogs.com/FLY-lai/p/18007930

相关文章

  • 在我的VS2019中重新配置2017项目生成的google test 项目
    原来的项目是其他版本的VS配置的，自己下载下来时候，本机也没有装GoogleTest所以用不起。如果重建项目在一个个引入工程代码太麻烦（文件多），所以我就想着有没有什么办法快捷配置，不用重建工程以下是我的一个配置方法，供大家交流学习：1.首先你本机要安装上GoogleTest，安装方法自查；2.如......
  • c++生成随机数
    产生随机数的叫随机数生发器生成随机数constunsignedzseed=time(0);voidsolve(){ //随机数生发器 mt19937_64m{zseed}; //种子 rep(i,1,5) cout<<m()<<endl; return;}重排序列constunsignedzseed=time(0);mt19937_64zgen{zseed};voidsolve(){ ve......
  • 踩坑了，MySQL数据库生成大量奇怪的大文件
    作者：田逸（formyz）一大早就收到某个数据库服务器磁盘满的报警信息，其中数据盘使用率超过90%，如下图所示。这是一台刚上线不久的MySQL从库服务器，数据盘的总容量是300G。先登录系统，查看主从同步是否正常，幸运的是主从同步正常；再看看磁盘空间的使用情况，执行的命令及输出如下。df-h[root@MyS......
  • vue的scoped中的class data-v-xxx生成规则为什么是按照文件的路径?
    Vue.js中，当在单文件组件（.vue文件）的<style>标签上使用scoped属性时，VueLoader会为组件中的CSS添加一个唯一的属性选择器，以确保样式只作用于当前组件内的元素。这个独特的属性通常格式为data-v-xxx，其中xxx是一个根据文件内容和路径生成的哈希值。生成规则基于文件内容和......
  • flex布局 自适应宽高 缩放到内容高度时不再进行缩放， 需求设置最小高度超出滚动条，并隐
    在需要滚动的元素内部添加一层div,并添加样式：position：absolute;父级样式添加 position:relative;即可<divclassName="pcCommon_left_top">          <divstyle={{position:'absolute',width:'calc(100%-72rem)'}}>     ......
  • 最小覆盖子串
    问题描述：给定一个字符串S和一个字符串T，请在S中找出包含T所有字母的最小子串。示例：输入:S="ADOBECODEBANC",T="ABC"输出:"BANC"说明：如果S中不存这样的子串，则返回空字符串""。如果S中存在这样的子串，我们保证它是唯一的答案。/***思路：*我们可以考......
  • 长度最小的子数组
    问题描述：给定一个含有n个正整数的数组和一个正整数s，找出该数组中满足其和≥s的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回0。示例:输入:s=7,nums=[2,3,1,2,4,3]输出:2解释:子数组[4,3]是该条件下的长度最小的连续子数组。进阶:如果你......
  • 【SSL协议】生成SSL证书
    目录生成SSL证书keytool相关指令说明服务器端SSL证书签发第一步：创建几个目录来保存证书第二步：生成server.keystore.jks文件（生成服务端的keystore文件）第三步：生成CA认证证书（ca-cert、ca-key）第四步：通过CA证书创建一个客户端信任证书（client.truststore.jks）第五步：通过CA证书创建一个服......
  • 2024年生成式AI芯片市场规模将达500亿美元
    1月24日，德勤发布《2024科技、传媒和电信行业预测》中文版报告，2024年是科技、传媒和电信行业关键的一年，不少科技公司正利用生成式AI升级软件和服务，预计今年全球生成式人工智能芯片销售额可能达到500亿美元以上。 2024年将有许多软件公司在产品中嵌入生成式AI，有些企业的产品将......
  • java代码实现自动生成数据库表er图
    最近有同事看到字节跳动产品设计文档里有数据库表er图。就想问问又没有现成的工具也给直接生成一个er图，经查找验证发现并没有。因为现在表关系都是用的逻辑外键而非物理外键约束的，所以像navicat等工具就算生成了也没有描述关系的连接线。那么为了满足需求，这边就略微出手写了个代码......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99