首页 > 其他分享 >最小生成树及扩展应用

最小生成树及扩展应用

时间：2024-04-07 23:30:04浏览次数：23  
标签：int dst py 扩展 最小 second edges 树及 px

文章目录

一、最小生成树

1.1 概念

给定一张边带权的无向图G = (V，E)，n = |V|，m = |E|，由V中全部 n 个顶点和E中 n - 1 条边构成的无向连通子图被称为G的一棵生成树。边的权值之和最小的生成树被称为无向图G的最小生成树(Minimum Spanning Tree, MST)。

1.2 定理一

1.2.1 内容

任意一棵最小生成树一定可以包含无向图中权值最小的边。

1.2.2 证明

反证法。假设无向图G = (V，E)的最小生成树不包含权值最小的边，那么我们把权值最小的边添加进树中，则会出现一个环。我们不妨设权值最小的边为<x, y, z>，我们任意去除掉环上一条权值大于z的边，则又得到一棵权值更小的生成树，与假设矛盾。故原命题成立。

1.2.3 推论

给定一个无向图G = (V, E)，n = |V|，m = |E|。从E中选出k < n - 1条边构成G的一个生成森林。若再从剩余的m - k条边中选择n - 1 - k条边添加到生成森林中，使其成为G的生成树，并且选出的边权之和最小，则该生成树一定可以包含m - k条边中连接生成森林的两个不连通节点的权值最小的边。

1.3 基于定理一推论的MST算法

1.3.1 Kruscal算法

1.3.1.1 算法原理

Kruskal算法就是基于上述推论的。Kruskal算法总是维护无向图的最小生成森林。

最初，可认为生成森林由0条边构成，每个节点各自构成一棵仅包含一个点的树。在任意时刻，Kruskal 算法从剩余的边中选出一条权值最小的，并且这条边的两个端点属于生成森林中两棵不同的树(不连通)，把该边加入生成森林。图中节点的连通情况可以用并查集维护。

1.3.1.2 算法流程
  1. 建立并查集，每个点各自构成一个集合。
  2. 把所有边按照权值从小到大排序，依次扫描每条边(x,y, z)。
  3. 若x，y属于同一集合（连通），则忽略这条边，继续扫描下一条。
  4. 否则，合并x，y所在的集合，并把z累加到答案中。
  5. 所有边扫描完成后，第4步中处理过的边就构成最小生成树。

时间复杂度为O(m logm)，可见Kruscal的时间复杂度很大程度上取决于图的稠密程度。

1.3.1.3 代码实现
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6005;
#define mkp make_pair
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
int n, p[N];	//并查集数组
PIII edges[N];	//边集数组
int findp(int x){	//并查集找根——路径压缩
    return p[x] < 0 ? x : p[x] = findp(p[x]);
}
bool merge(int x, int y){	//并查集合并——按秩合并
    int px = findp(x), py = findp(y);
    if(px == py) return true;
    if(p[px] > p[py]) swap(px, py);
    p[px] += p[py], p[py] = px;
    return false;
}
int main(){
    memset(p, -1, sizeof p);	//并查集初始化
    cin >> n;
    for(int i = 0, a, b, c; i < n - 1; i++) cin >> a >> b >> c, edges[i] = mkp(c, mkp(a, b));
    sort(edges, edges + n - 1);
    int res = 0;
    for(int i = 0; i < n - 1; i ++){
        int x = edges[i].second.first, y = edges[i].second.second, w = edges[i].first;
        if(merge(x, y)) res += w;
    }
    cout << res << '\n';
    return 0;
}

1.3.2 Prim算法

1.3.2.1 算法原理

Prim算法同样基于上述推论，但思路略有改变。Prim算法总是维护最小生成树的一部分。

最初，Prim 算法仅确定1号节点属于最小生成树。
在任意时刻，设已经确定属于最小生成树的节点集合为T，剩余节点集合为S。
Prim算法找到到T集合最近的节点x，然后把点x从集合S中删除，加入到集合T，并把合并前x到T的距离累加到答案中。

具体来说，可以维护数组dst：若x∈S，则dst[x]表示节点x与集合T中的节点之间权值最小的边的权值。若x∈T，则dst[x] 就等于x被加入T时选出的最小边的权值。

可以类比Djkstra算法，用一个数组标记节点是否属于T。每次从未标记的节点中选出dst值最小的，把它标记(新加入T)，同时扫描所有出边，更新另一个端点的dst值。最后，最小生成树的权值总和就是Σdst[]

Prim算法的时间复杂度为O(n^2)，可以用二叉堆优化到O(m logn)。 但用二叉堆优化不如直接使用Kruskal算法更加方便。因此，Prim 主要用于稠密图，尤其是完全图的最小生成树的求解。

1.3.2.2 算法流程
  1. dst[]初始为正无穷，dst[1] = 0，T = { 1 }，优先级队列pq初始存放<dst[1], 1>
  2. 每轮从堆顶弹出当前距离T最近的节点u，标记u入T
  3. 从u开始松弛其未标记的邻接点到T的距离
  4. 堆空则算法结束
1.3.2.3 代码实现

懒得敲前向星存图的代码了，拿了个练习题的代码，不过是邻接矩阵存图

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;

const int N = 305;
int n, g[N][N], dst[N];	//邻接矩阵存图
bool vis[N];
int prim(){
	memset(dst, 0x3f, sizeof dst);	//初始化距离为正无穷
	priority_queue<PII, vector<PII>, greater<PII>> pq;
	pq.emplace(dst[1] = 0, 1);
	int res = 0;
	while(pq.size()){
		PII t = pq.top();
		pq.pop();
		int w = t.first, u = t.second;
		if(vis[u]) continue;
		vis[u] = 1;
		res += w;
		for(int i = 1; i <= n + 1; i++)
			if(!vis[i] && dst[i] > g[u][i])
				pq.emplace(dst[i] = g[u][i], i);
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> g[i][n + 1], g[n + 1][i] = g[i][n + 1];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			cin >> g[i][j];
	cout << prim();
	return 0;
}

二、OJ练习

2.1 POJ 1258 Agri-Net

2.1.1 原题链接

1258 – Agri-Net (poj.org)

2.1.2 思路分析

MST板子题，数据量挺小的，直接邻接矩阵存图，写prim（邻接矩阵存图的时候prim板子写起来还是很舒服的）

2.1.3 AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define mkp make_pair
typedef pair<int, int> PII;
const int N = 105, M = N * N;

int n, g[N][N], dst[N];
bool vis[N];
int main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	while(cin >> n){
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				cin >> g[i][j];
		memset(dst, 0x3f, sizeof dst), memset(vis, 0, sizeof vis);
		priority_queue<PII, vector<PII>, greater<PII>> pq;
		pq.push(mkp(dst[1] = 0, 1));
		int res = 0;
		while(pq.size()){
			PII t = pq.top();
			pq.pop();
			int u = t.second, d = t.first;
			if(vis[u]) continue;
			vis[u] = 1;
			res += d;
			for(int i = 1; i <= n; i++){
				if(vis[i]) continue;
				if(g[u][i] < dst[i]) pq.push(mkp(dst[i] = g[u][i], i));
			}
		}
		cout << res << '\n';
	}
	return 0;
}

2.2 POJ1287Networking

2.2.1 原题链接

1287 – Networking (poj.org)

2.2.2 思路分析

MST板子题，这个题写Kruscal的板子

2.2.3 AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define mkp make_pair
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
const int N = 55, M = N * N;

int n, m, p[N];

int findp(int x){
	return p[x] < 0 ? x : p[x] = findp(p[x]);
}
void merge(int x, int y){
	int px = findp(x), py = findp(y);
	if(px == py) return;
	if(p[px] > p[py]) swap(px, py);
	p[px] += p[py], p[py] = px;
}
int Kruscal(){
	int res = 0;
	priority_queue<PIII, vector<PIII>, greater<PIII>> pq; 
	for(int i = 0, a, b, c; i < m; i++){
		cin >> a >> b >> c;
		pq.push(mkp(c, mkp(a, b)));
	}
	memset(p, -1, sizeof p);
	while(pq.size()){
		PIII t = pq.top();
		pq.pop();
		int w = t.first, u = t.second.first, v = t.second.second;
		if(findp(u) == findp(v)) continue;
		merge(u, v), res += w;
	}
	return res;
}
int main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	while(cin >> n, n){
		cin >> m;
		cout << Kruscal() << '\n';	
	}
	return 0;
}

2.3 联络员(liaison)

2.3.1 原题链接

Problem Detail - 联络员(liaison) - oj (noip.ac.cn)

2.3.2 思路分析

将所有必须拿的边先拿进来同时把并查集也维护下，然后跑Kruscal即可

2.3.3 AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define mkp make_pair
const int N = 2005, M = 10005;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

int n, m, tot, ans, p[N];
PIII edges[M];
int findp(int x){
	return p[x] < 0 ? x : p[x] = findp(p[x]);
}
void merge(int x, int y){
	int px = findp(x), py = findp(y);
	if(px == py) return;
	if(p[px] > p[py]) swap(px, py);
	p[px] += p[py], p[py] = px;
}

int main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	memset(p, -1, sizeof p);
	cin >> n >> m;
	for(int i = 0, a, b, c, d; i < m; i++){
		cin >> a >> b >> c >> d;
		if(a == 1)
			ans += d, merge(b, c);
		else
			edges[tot++] = mkp(d, mkp(b, c));
	}
	sort(edges, edges + tot);
	for(int i = 0; i < tot; i++)
		if(findp(edges[i].second.first) != findp(edges[i].second.second))
			ans += edges[i].first, merge(edges[i].second.first, edges[i].second.second);
	cout << ans;
	return 0;
}

2.4 连接格点(grid)

2.4.1 原题链接

[Problem Detail - 连接格点(grid) - oj (noip.ac.cn)](http://ybt.ssoier.cn:8088/problem_show.php?pid=1394)

2.4.2 思路分析

看成每个格子向右向下伸出两条边，那么原图可以建立O(M * N * 2)的边

我们先将已经连接的点用并查集维护

然后我们发现朝下的边权都是1，朝右的边权都是2，那么我们就不需要进行排序，先遍历朝下的边，再遍历朝右的边就已经有序了，直接跑Kruscal即可

时间复杂度为O(MN)，也就1e6量级

2.4.3 AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define mkp make_pair
const int N = 1005, M = (N * N) << 1;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

int n, m, tot, ans, p[N * N];
int findp(int x){
	return p[x] < 0 ? x : p[x] = findp(p[x]);
}
void merge(int x, int y){
	int px = findp(x), py = findp(y);
	if(px == py) return;
	if(p[px] > p[py]) swap(px, py);
	p[px] += p[py], p[py] = px;
}

int main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	memset(p, -1, sizeof p);
	cin >> m >> n;
	int a, b, c, d;
	while(cin >> a >> b >> c >> d)
		merge(a * n + b, c * n + d);	
	for(int i = 1; i < m; i++)
		for(int j = 1; j <= n; j++)
			if(findp(i * n + j) != findp((i + 1) * n + j))		
				merge(i * n + j, (i + 1) * n + j), ans ++;
	for(int i = 1; i <= m; i++)
		for(int j = 1; j < n; j++)
			if(findp(i * n + j) != findp(i * n + j + 1))
				merge(i * n + j, i * n + j + 1), ans += 2;

	cout << ans;
	return 0;
}

2.4 「一本通 3.1 练习 1」新的开始

2.4.1 原题链接

#10066. 「一本通 3.1 练习 1」新的开始 - 题目 - LibreOJ (loj.ac)

2.4.2 思路分析

建立虚拟节点，向原图节点连接一条边权为点权的边，然后求最小生成树即可

2.4.3 AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;

const int N = 305;
int n, g[N][N], dst[N];
bool vis[N];
int prim(){
	memset(dst, 0x3f, sizeof dst);
	priority_queue<PII, vector<PII>, greater<PII>> pq;
	pq.emplace(dst[1] = 0, 1);
	int res = 0;
	while(pq.size()){
		PII t = pq.top();
		pq.pop();
		int w = t.first, u = t.second;
		if(vis[u]) continue;
		vis[u] = 1;
		res += w;
		for(int i = 1; i <= n + 1; i++)
			if(!vis[i] && dst[i] > g[u][i])
				pq.emplace(dst[i] = g[u][i], i);
	}
	return res;
}
int main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> g[i][n + 1], g[n + 1][i] = g[i][n + 1];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			cin >> g[i][j];
	cout << prim();
	return 0;
}

2.5 洛谷 P1991 无线通讯网

2.5.1 原题链接

P1991 无线通讯网 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

2.5.2 思路分析

问题即求一个最小的d，使得去除所有边权大于d的边后，原图连通块个数小于等于p。

我们按照边权升序排序，然后顺序遍历，用并查集维护连通块即可

2.5.3 AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define sc scanf
#define mkp make_pair
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<double, PII> PDII;
const int N = 505;
int k, n, tot, p[N];
PII pos[N];
PDII edges[N * N];
double getdst(int i, int j){
	double dx = pos[i].first - pos[j].first, dy = pos[i].second - pos[j].second;
	return sqrt(dx * dx + dy * dy);
}
int findp(int x){
	return p[x] < 0 ? x : p[x] = findp(p[x]);
}
bool merge(int x, int y){
	int px = findp(x), py = findp(y);
	if(px == py) return false;
	if(p[px] > p[py]) swap(px, py);
	p[px] += p[py], p[py] = px;
	return true; 
}
int main(){
	//freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	memset(p, -1, sizeof p);
	cin >> k >> n;
	for(int i = 1; i <= n; i++) sc("%d%d", &pos[i].first, &pos[i].second);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j < i; j++)
			edges[tot++] = mkp(getdst(i, j), mkp(i, j));
	sort(edges, edges + tot);
	double ans = 0;
	for(int i = 0, s = n; i < tot && s > k; i++){
		int x = edges[i].second.first, y = edges[i].second.second;
		if(merge(x, y))
			s--, ans = edges[i].first;
	}
	printf("%.2lf", ans);
	return 0;
}

2.6 ACWING346. 走廊泼水节

2.6.1 原题链接

346. 走廊泼水节 - AcWing题库

2.6.2 思路分析

我们在Kruscal的基础上加以修改

每次拿一条边连接两个连通块可以看作连接两个完全图，那么两个完全图连接后需要添加一些边构成一个新的完全图，添加边的数目就是

(左完全图点数目 * 右完全图点数目 - 1) * (所选边权+1)，减去的1是选的那条边，添加的边必须选的边都大，所以是+1

2.6.3 AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6005;
#define mkp make_pair
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
int n, p[N];
PIII edges[N];
int findp(int x){
    return p[x] < 0 ? x : p[x] = findp(p[x]);
}
int merge(int x, int y, int w){
    int px = findp(x), py = findp(y);
    if(px == py) return 0;
    int res = (p[px] * p[py] - 1) * (w + 1);
    if(p[px] > p[py]) swap(px, py);
    p[px] += p[py], p[py] = px;
    return res;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int _ = 1;
    cin >> _;
    while(_--){
        memset(p, -1, sizeof p);
        cin >> n;
        for(int i = 0, a, b, c; i < n - 1; i++) cin >> a >> b >> c, edges[i] = mkp(c, mkp(a, b));
        sort(edges, edges + n - 1);
        int res = 0;
        for(int i = 0; i < n - 1; i ++){
            int x = edges[i].second.first, y = edges[i].second.second, w = edges[i].first;
            res += merge(x, y, w);
        }
        cout << res << '\n';
    }
    return 0;
}

三、 最小瓶颈生成树

3.1 概念

对于图 G 中的生成树，树上最大的边权值在所有生成树中最小。

3.2 结论

最小生成树和最小瓶颈生成树等价

我们在下面这道题目中进行证明

3.3练习——洛谷P2330SCOI2005] 繁忙的都市

3.3.1 原题链接

[P2330 SCOI2005] 繁忙的都市 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

3.3.2 思路分析

1、选一些边让图连通

2、边尽可能少——树

3、选的边的最大值尽可能小

  • 最大的最小可以用二分，一种思路就是二分答案，通过并查集来判断选择所有权值不超过答案的边能否使得原图连通
  • 当然我们也可以用最小生成树，事实上，最小生成树可以满足条件3，证明：
    • 我们将边预排序，遍历边
    • 对于<a, b>，如果连通就不管
    • 如果不连通，那么该边一定可以被包含在答案内，因为如果该条边不选，那么最终答案中a，b的路径上一定存在比该边权值大的边（根据推论易得），那么我们进行替换即可。
    • 所以最后添加进最小生成树的边就是3的答案

通过这道题我们可以得出结论：最小生成树和最小瓶颈生成树等价

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define mkp make_pair
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
const int N = 305, M = 8005;

int n, m, p[N];
PIII edges[M];
int findp(int x){
	return p[x] < 0 ? x : p[x] = findp(p[x]);
}
void merge(int x, int y){
	int px = findp(x), py = findp(y);
	if(px == py) return;
	if(p[px] > p[py]) swap(px, py);
	p[px] += p[py], p[py] = px;
}
int Kruscal(){
	memset(p, -1, sizeof p);
	int res = 0;
	for(int i = 0, a, b, c; i < m; i++)
		cin >> a >> b >> c, edges[i] = mkp(c, mkp(a, b));
	sort(edges, edges + m);
	for(int i = 0; i < m; i++)
		if(findp(edges[i].second.first) != findp(edges[i].second.second))
			merge(edges[i].second.first, edges[i].second.second), res = edges[i].first;	
	return res;
}
int main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	cout << n - 1 << ' ' << Kruscal();
	return 0;
}

四、次小生成树

4.1 概念

次小生成树可以分为严格次小生成树和非严格次小生成树。 即权值小于最小生成树的生成树中最大的和权值小于等于最小生成树的生成树中最大的。

设T为图G的一棵生成树，对于非树边a和树边b，插入边a，并删除边b的操作记为(+a, -b)。如果T+a -b 之后，仍然是一棵生成树，称(+a，-b)是T的一个可行交换。称由T进行一 次可行变换所得到的新的生成树集合称为T的邻集。

4.2 定理

次小生成树一定在最小生成树的邻集中。

证明

反证法。我们假设次小生成树存在两条边不同，那么将在最小生成树中不在次小生成树中的一条边拿出放入次小生成树便会构成一个环，那么环上会存在一条在次小生成树中而不在最小生成树中的边，我们删去这条边，便得到了比次小生成树小而比最小生成树小的生成树，与假设矛盾，故原命题成立。

4.3 OJ练习

4.3.1 洛谷[P4180 [BJWC2010] 严格次小生成树

4.3.1.1 原题链接

[P4180 BJWC2010] 严格次小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

4.3.1.2 思路分析

我们显然只需要找到不同的那条边即可

那么我们先进行一次Kruscal算法，然后标记所有用到的边

然后枚举所有没有用到的边去进行替换，那么应该如何替换呢？

我们任意添加一条没有用到的边就会产生一个环。然后需要从环中拿掉一条边来得到一棵生成树

我们记新加入边的边权为w，环中最大边权为d1，严格次大边权为d2

那么显然有 w >= d1

如果w > d1，那么我们用w替换d1就可以得到一个候选答案

如果w == d1，那么我们的生成树边权和是没有变的，所以不能选择（事实上，它只能是非严格次小生成树的候选），此时就需要和严格次大边权d2进行替换来得到候选答案，因为w > d2，这是毫无疑问的

这就要求我们能够快速的得到树上一条路径上的边权最大值，我们可以用ST表求LCA或者树链剖分等方法。

由于树链剖分会多一个log所以这里选择ST表求LCA

4.3.1.3 AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
const int N = 1e5 + 10, M = 3e5 + 10, H = 18, inf = 1e9;

int n, m;
int p[N];
int dep[N], fa[N][H], d1[N][H], d2[N][H];
int head[N], idx;
PIII es[M];
bool used[M];

struct edge{
    int v, w, nxt;
}edges[M << 1];

void addedge(int u, int v, int w){
    edges[idx] = { v, w, head[u] }, head[u] = idx++;
}
void add(int u, int v, int w){
    addedge(u, v, w), addedge(v, u, w);
}

int findp(int x){
    return p[x] < 0 ? x : p[x] = findp(p[x]);
}

bool merge(int x, int y){
    int px = findp(x), py = findp(y);
    if(px == py) return false;
    if(p[px] > p[py]) swap(px, py);
    p[px] += p[py], p[py] = px;
    return true;
}

LL Kruscal(){
    sort(es, es + m);
    LL res = 0;
    for(int i = 0; i < m; i++){
        int u = es[i].second.first, v = es[i].second.second, w = es[i].first;
        if(used[i] = merge(u, v)) res += w;
    }
    return res;
}

void dfs(int u, int father, int w){
	dep[u] = dep[father] + 1;
	fa[u][0] = father, d1[u][0] = w, d2[u][0] = -inf;
	for(int i = 1; i < H; i++){
	    fa[u][i] = fa[fa[u][i - 1]][i - 1];
	    int dst[4] = { d1[u][i - 1], d1[fa[u][i - 1]][i - 1], d2[u][i - 1], d2[fa[u][i - 1]][i - 1] };
	    d1[u][i] = d2[u][i] = -inf;
	    for(int j = 0; j < 4; j++){
	        if(dst[j] > d1[u][i]) d2[u][i] = d1[u][i], d1[u][i] = dst[j];
	        else if(dst[j] != d1[u][i] && dst[j] > d2[u][i]) d2[u][i] = dst[j];
	    }   
	}
	for(int i = head[u]; ~i; i = edges[i].nxt){
	    int v = edges[i].v;
	    if(v != father)
	        dfs(v, u, edges[i].w);
	}
}

int lca(int x, int y, int w){
    static int dst[N << 1];
    int cnt = 0;
	if(dep[x] < dep[y]) 
	    swap(x, y);
	for(int i = H - 1; i >= 0; i--)
	    if(dep[fa[x][i]] >= dep[y]){
	        dst[cnt ++] = d1[x][i];
	        dst[cnt ++] = d2[x][i];
	        x = fa[x][i];
	    }
	if(x != y){ 
	    for(int i = H - 1; i >= 0; i--)
	        if(fa[x][i] != fa[y][i]){
	            dst[cnt ++] = d1[x][i];
	            dst[cnt ++] = d2[x][i];
	            dst[cnt ++] = d1[y][i];
	            dst[cnt ++] = d2[y][i];
	            x = fa[x][i], y = fa[y][i];
	        }
	    dst[cnt ++] = d1[x][0];
	    dst[cnt ++] = d1[y][0];
	}
	int dst1 = -inf, dst2 = -inf;
	for(int i = 0; i < cnt; i++){
	    if(dst[i] > dst1)   dst2 = dst1, dst1 = dst[i];
	    else if(dst[i] != dst1 && dst[i] > dst2) dst2 = dst[i];
	}
	if(w > dst1) return w - dst1;
	if(w > dst2) return w - dst2;
	return inf;
}


void build(){
    for(int i = 0; i < m; i++){
        int u = es[i].second.first, v = es[i].second.second, w = es[i].first;
        if(used[i]) add(u, v, w);
    }
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    memset(head, -1, sizeof head), memset(p, -1, sizeof p);
    cin >> n >> m;
    for(int i = 0; i < m; i++)
        cin >> es[i].second.first >> es[i].second.second >> es[i].first;
    LL sum = Kruscal();
    build();
    dfs(1, 0, -inf);
    LL  res = 1e18;
    for(int i = 0; i < m; i++){
        if(!used[i]){
            int u = es[i].second.first, v = es[i].second.second, w = es[i].first;
            res = min(res, sum + lca(u, v, w));
        }
    }
    cout << res;
    return 0;
}

4.3.2「一本通 3.1 练习 3」秘密的牛奶运输

4.3.2.1 原题链接

#10068. 「一本通 3.1 练习 3」秘密的牛奶运输 - 题目 - LibreOJ (loj.ac)

4.3.2.2 思路分析

和上道题一样，求次小生成树

4.3.2.3 AC代码

ST lca

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
#define int long long
typedef long long LL;
const int N = 505, M = 1e4 + 10, H = 10;
const int inf = 1e18;
struct{
	int v, w, nxt;
}edges[M << 1];
int head[N], p[N], idx, n, m;
int fa[N][H], d1[N][H], d2[N][H], dep[N];
PIII es[M];
bool used[M];
int findp(int x){
	return p[x] < 0 ? x : p[x] = findp(p[x]);
}
bool merge(int x, int y){
	int px = findp(x), py = findp(y);
	if(px == py) return false;
	if(p[px] > p[py]) swap(px, py);
	p[px] += p[py], p[py] = px;
	return true;
}
void addedge(int u, int v, int w){
	edges[idx] = { v, w, head[u] }, head[u] = idx++;
}
void add(int u, int v, int w){
	addedge(u, v, w), addedge(v, u, w);
}
void dfs(int x, int father, int w){
	dep[x] = dep[father] + 1;
	fa[x][0] = father, d1[x][0] = w, d2[x][0] = -inf;
	for(int i = 1; i < H; i++){
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
		int dst[4] = { d1[x][i - 1], d2[x][i - 1], d1[fa[x][i - 1]][i - 1], d2[fa[x][i - 1]][i - 1] };
		for(int d : dst)
			if(d > d1[x][i]) d2[x][i] = d1[x][i], d1[x][i] = d;
			else if(d != d1[x][i] && d > d2[x][i]) d2[x][i] = d;
	}
	for(int i = head[x]; ~i; i = edges[i].nxt){
		int y = edges[i].v;
		if(y != father) dfs(y, x, edges[i].w);
	}
}
int lca(int x, int y, int w){
	static int dst[N << 1];
	int cnt = 0;
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = H - 1; i >= 0; i--)	
		if(dep[fa[x][i]] >= dep[y]){
			dst[cnt++] = d1[x][i];
			dst[cnt++] = d2[x][i];
			x = fa[x][i];
		}
	if(x != y){
		for(int i = H - 1; i >= 0; i--)
			if(fa[x][i] != fa[y][i]){
				dst[cnt++] = d1[x][i];
				dst[cnt++] = d2[x][i];
				dst[cnt++] = d1[y][i];
				dst[cnt++] = d2[y][i];
				x = fa[x][i], y = fa[y][i];
			}
			dst[cnt++] = d1[x][0];
			dst[cnt++] = d1[y][0];
	}
	int dst1 = -inf, dst2 = -inf;
	for(int i = 0; i < cnt; i++)
		if(dst[i] > dst1) dst2 = dst1, dst1 = dst[i];
		else if(dst[i] != dst1 && dst[i] > dst2) dst2 = dst[i];
	if(w > dst1) return w - dst1;
	return w - dst2;
}
int Kruscal(){
	sort(es, es + m);
	int res = 0;
	for(int i = 0; i < m; i++)
		if(used[i] = merge(es[i].second.first, es[i].second.second)) res += es[i].first;
	return res;
}
void build(){
	for(int i = 0; i < m; i++)
		if(used[i])
			add(es[i].second.first, es[i].second.second, es[i].first);
}
signed main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	memset(p, -1, sizeof p), memset(head, -1, sizeof head);
	cin >> n >> m;
	for(int i = 0; i < m; i++) cin >> es[i].second.first >> es[i].second.second >> es[i].first; 
	int sum = Kruscal();
	build();
	dfs(1, 0, -inf);
	int res = 1e18;
	for(int i = 0; i < m; i++)
		if(!used[i])
			res = min(res, sum + lca(es[i].second.first, es[i].second.second, es[i].first));
	cout << res;
	return 0;
}

树链剖分

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
#define lc rt << 1
#define rc rt << 1 | 1
typedef long long LL;
const int N = 505, M = 1e4 + 10, H = 10;
const int inf = 1e18;
struct{
	int v, w, nxt;
}edges[M << 1];
int head[N], p[N], idx, n, m, tot;
int fa[N], son[N], d[N], sz[N], w[N], nw[N], dfn[N], top[N];
PIII es[M];
bool used[M];
int findp(int x){
	return p[x] < 0 ? x : p[x] = findp(p[x]);
}
bool merge(int x, int y){
	int px = findp(x), py = findp(y);
	if(px == py) return false;
	if(p[px] > p[py]) swap(px, py);
	p[px] += p[py], p[py] = px;
	return true;
}
void addedge(int u, int v, int w){
	edges[idx] = { v, w, head[u] }, head[u] = idx++;
}
void add(int u, int v, int w){
	addedge(u, v, w), addedge(v, u, w);
}
struct node{
	int s1, s2, l, r;
}tr[N << 2];
void pushup(int rt){
	tr[rt].s1 = tr[lc].s1, tr[rt].s2 = tr[lc].s2;
	if(tr[rc].s1 > tr[rt].s1) tr[rt].s2 = tr[rt].s1, tr[rt].s1 = tr[rc].s1;
	if(tr[rc].s2 != tr[rc].s1 && tr[rc].s2 > tr[rt].s2) tr[rt].s2 = tr[rc].s2;
}

void build(int rt, int l, int r){
	tr[rt] = { nw[l], -inf, l, r };
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(lc, l, mid), build(rc, mid + 1, r);
	pushup(rt); 
} 
PII query(int rt, int l, int r){
	if(l <= tr[rt].l && tr[rt].r <= r){
		return make_pair(tr[rt].s1, tr[rt].s2);
	}
	int mid = (tr[rt].l + tr[rt].r) >> 1;
	int dst1 = -inf, dst2 = -inf;
	if(l <= mid) {
		PII t = query(lc, l, r);
		dst1 = t.first, dst2 = t.second;
	}
	if(mid < r) {
		PII t = query(rc, l, r);
		if(t.first > dst1) dst2 = dst1, dst1 = t.first;
		if(t.second != dst1 && t.second > dst2) dst2 = t.second;
	}
	return make_pair(dst1, dst2);
}

void dfs1(int x, int father){
	d[x] = d[father] + 1, fa[x] = father, sz[x] = 1;
	for(int i = head[x]; ~i; i = edges[i].nxt){
		int y = edges[i].v;
		if(y == father) continue;
		w[y] = edges[i].w;
		dfs1(y, x);
		sz[x] += sz[y];
		if(sz[son[x]] < sz[y]) son[x]= y;
	}
}
void dfs2(int x, int t){
	top[x] = t, nw[dfn[x] = ++tot] = w[x];
	if(!son[x]) return;
	dfs2(son[x], t);
	for(int i = head[x]; ~i; i = edges[i].nxt){
		int y = edges[i].v;
		if(!dfn[y])
			dfs2(y, y);
	}
}
int query_path(int x, int y, int w){
	static int dst[N << 1];
	int cnt = 0;
	while(top[x] != top[y]){
		if(d[top[x]] < d[top[y]]) swap(x, y);
		PII t = query(1, dfn[top[x]], dfn[x]);
		dst[cnt++] = t.first;
		dst[cnt++] = t.second;
		x = fa[top[x]];
	}
	if(x != y){
		if(d[x] < d[y]) swap(x, y);
		PII t = query(1, dfn[son[y]], dfn[x]);
		dst[cnt++] = t.first;
		dst[cnt++] = t.second;
	}
	int dst1 = -inf, dst2 = -inf;
	for(int i = 0; i < cnt; i++)
		if(dst[i] > dst1) dst2 = dst1, dst1 = dst[i];
		else if(dst[i] != dst1 && dst[i] > dst2) dst2 = dst[i];
	if(w > dst1) return w - dst1;
	return w - dst2;
}
int Kruscal(){
	sort(es, es + m);
	int res = 0;
	for(int i = 0; i < m; i++)
		if(used[i] = merge(es[i].second.first, es[i].second.second)) res += es[i].first;
	return res;
}
void build_mp(){
	for(int i = 0; i < m; i++)
		if(used[i])
			add(es[i].second.first, es[i].second.second, es[i].first);
}
signed main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	memset(p, -1, sizeof p), memset(head, -1, sizeof head);
	cin >> n >> m;
	for(int i = 0; i < m; i++) cin >> es[i].second.first >> es[i].second.second >> es[i].first; 
	int sum = Kruscal();
	build_mp();
	w[1] = -inf, dfs1(1, 0), dfs2(1, 1), build(1, 1, tot);
	int res = 1e18;
	for(int i = 0; i < m; i++)
		if(!used[i])
			res = min(res, sum + query_path(es[i].second.first, es[i].second.second, es[i].first));
	cout << res;
	return 0;
}

标签：int,dst,py,扩展,最小,second,edges,树及,px
From： https://blog.csdn.net/EQUINOX1/article/details/137378215

相关文章

  • python学习--基础知识（字符串扩展）
    八、字符串扩展1、字符串的三种定义方式2、字符串的拼接3、字符串的格式化4、字符串格式化的精确度控制5、字符串格式化的快速方法6、字符串格式化--对表达式进行格式化......
  • 最小化安装Ubutun后的初始化操作
    最小化安装Ubutun后的初始化操作由于Ubutub相关配置路径与红帽系操作系统有些差异，这边进行一些简单初始化记录。使用的操作系统镜像为：ubuntu-20.04.6-desktop-amd64.iso1.root账户配置使用该镜像安装系统，没有红帽系安装过程中对root用户的配置。需要进入系统后使用sudopassw......
  • 最小栈
    题目设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。实现 MinStack 类:MinStack() 初始化堆栈对象。voidpush(intval) 将元素val推入堆栈。voidpop() 删除堆栈顶部的元素。inttop() 获取堆栈顶部的元素。intgetMin() 获取堆栈中的最......
  • C++ //练习 11.14 扩展你在11.2.1节练习（第378页）中编写的孩子姓到名的map，添加一个pair
    C++Primer（第5版）练习11.14练习11.14扩展你在11.2.1节练习（第378页）中编写的孩子姓到名的map，添加一个pair的vector，保存孩子的名和生日。环境：LinuxUbuntu（云服务器）工具：vim 代码块/************************************************************************* >Fil......
  • JavaScript中，...（三个点）是扩展运算符
    在JavaScript中，...（三个点）是扩展运算符（SpreadOperator）和剩余参数（RestParameters）的语法。它确实可以用来“展开”对象的属性或数组的元素。展开对象的属性对于对象，扩展运算符可以用来将一个对象的所有可枚举属性复制到新对象中，或者与现有的对象属性合并。javascript复制代码......
  • EAS_复制已有字段的值到DEP扩展的字段上
    1、实体字段如图  金额（amountTxt)为要复制的字段，测试字段（test）目标字段，现在要在提交后，将金额字段的值复制到测试字段（test）上，可以在对应的方法添加前置脚本，添加的地方一般在提交，保存，更新方法上；2、具体操作；选择对应扩展实体》扩展定义选择对应的方法，这里注意，不同的方法，由于......
  • linux扩展正则表达式()
    1.()含义linux扩展正则表达式()含义是找出“用户组”字符串；此外，()还可以用来作为“多个重复用户组”的识别2.样例命令1：grep-nE'p(wp|lp|np|dp)o'anaconda-ks.cfgORegrep-n 'p(wp|lp|np|dp)o'anaconda-ks.cfg#搜索包含(pwpo)、(plpo)、(pnpo)、(pdpo)字符串的行，因......
  • Java-字符知识扩展
    4.6字符扩展1.字符的强制转换所有的字符本质还是数字2.转义字符：3.布尔值扩展搬砖好累呜呜呜......
  • 【RISC-V 指令集】RISC-V 向量V扩展指令集介绍(八)- 向量整数算术指令
     1.引言以下是《riscv-v-spec-1.0.pdf》文档的关键内容：这是一份关于向量扩展的详细技术文档，内容覆盖了向量指令集的多个关键方面，如向量寄存器状态映射、向量指令格式、向量加载和存储操作、向量内存对齐约束、向量内存一致性模型、向量算术指令格式、向量整数和浮点算术指......
  • 【RISC-V 指令集】RISC-V 向量V扩展指令集介绍(七)- 向量算术指令格式
      1.引言以下是《riscv-v-spec-1.0.pdf》文档的关键内容：这是一份关于向量扩展的详细技术文档，内容覆盖了向量指令集的多个关键方面，如向量寄存器状态映射、向量指令格式、向量加载和存储操作、向量内存对齐约束、向量内存一致性模型、向量算术指令格式、向量整数和浮点算术......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99