NOI大纲——提高组—

NOI大纲——提高组——最小生成树

本文主要是介绍NOI大纲——提高组——最小生成树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最小生成树

简介

一个图中可能存在多条相连的边,我们**一定可以从一个图中挑出一些边生成一棵树。**这仅仅是生成一棵树,还未满足最小,当图中每条边都存在权重时,这时候我们从图中生成一棵树(n - 1 条边)时,生成这棵树的总代价就是每条边的权重相加之和。

一个有N个点的图，边一定是大于等于N-1条的。图的最小生成树，就是在这些边中选择N-1条出来，连接所有的N个点。这N-1条边的边权之和是所有方案中最小的。

应用

1.城市规划

要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

2.游戏开发

游戏的本质其实都是迷宫，比如王者荣耀的地图，以俯视的角度来看，他就是一个迷宫，只不过进行了建模，而对于每一个迷宫，必须要联通，也就是要走的通，那么我们就可以使用最小生成树的算法了。

Prim 普里姆算法

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 505;int a[maxn][maxn];//临界矩阵存储
int vis[maxn],dist[maxn];//vis为标记数组，dist为距离数组
int n,m;
int u,v,w;
long long sum = 0;//存储答案// 使用 Prim 算法计算最小生成树的权值和
int prim(int pos) {dist[pos] = 0;  // 初始化，将起始点到自身的距离设为 0// 一共有 n 个点，需要遍历 n 次，每次寻找一个权值最小的点，记录其下标for(int i = 1; i <= n; i++) {int cur = -1;  // 用于记录当前找到的最小距离的点的下标// 寻找未访问过的点中距离最小的点for(int j = 1; j <= n; j++) {if(!vis[j] && (cur == -1 || dist[j] < dist[cur])) {cur = j;  // 更新当前最小距离的点的下标}}// 如果最小的距离都为极大值则不可能形成最小生成树，提前终止if(dist[cur] >= INF) return INF;sum += dist[cur];  // 记录答案，将当前找到的最小距离加入到最小生成树的权值和中vis[cur] = 1;  // 标记当前找到的最小距离的点为已访问// 更新与当前找到的最小距离的点相连的其他点的距离for(int k = 1; k <= n; k++) {// 只更新还没有找到的最小权值if(!vis[k]) dist[k] = min(dist[k], a[cur][k]);}}return sum;  // 返回最小生成树的权值和
}int main() {cin>>n>>m;memset(a,0x3f,sizeof(a));memset(dist,0x3f,sizeof(dist));//附上极大值for(int i = 1; i <= m; i ++) {cin>>u>>v>>w;a[u][v] = min(a[u][v],w);a[v][u] = min(a[v][u],w);//去除重边}int value = prim(1);if(value >= INF) cout<<"impossible";else cout<<sum;return 0;
}

Kruskal 克鲁斯卡尔算法

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10; 
struct node {int x,y,z;
}edge[maxn];
bool cmp(node a,node b) {return a.z < b.z;//以长度为基准
}
int fa[maxn];
int n,m;
int u,v,w; 
long long sum;int get(int x) {//并查集找祖宗return x == fa[x] ? x : fa[x] = get(fa[x]);
}int main() {cin>>n>>m;for(int i = 1; i <= m; i ++) {cin>>edge[i].x>>edge[i].y>>edge[i].z;}for(int i = 0; i <= n; i ++) {//并查集初始化fa[i] = i;}sort(edge + 1,edge + 1 + m,cmp);//排序// 每次加入一条最短的边for(int i = 1; i <= m; i ++) {int x = get(edge[i].x);int y = get(edge[i].y);//找祖宗if(x == y) continue;//如果祖宗一样则为环，所以跳过fa[y] = x;//合并sum += edge[i].z;//存储答案}int ans = 0;for(int i = 1; i <= n; i ++) {if(i == fa[i]) ans ++;//如果有点没有被最小生成树所包含，则增加}if(ans > 1) cout<<"impossible";//按理来说应该只有一个，也就是所有人的祖先else cout<<sum;return 0;
}