NO.92十六届蓝桥杯备战|图论基础-最小生成树-Prim算法-Kruskal算法|买礼物|繁忙的都市|滑雪(C++)

一个具有n个顶点的连通图，其⽣成树为包含n-1条边和所有顶点的极⼩连通⼦图。对于⽣成树来说，若砍去⼀条边就会使图不连通图；若增加⼀条边就会形成回路。

⼀个图的⽣成树可能有多个，将所有⽣成树中权值之和最⼩的树称为最⼩⽣成树。
构造最⼩⽣成树有多种算法，典型的有普利姆(Prim)算法和克鲁斯卡尔(Kruskal)算法两种，它们都是基于贪⼼的策略。

Prim算法

核⼼：不断加点。
Prim 算法构造最⼩⽣成树的基本思想：

1. 从任意⼀个点开始构造最⼩⽣成树；
2. 将距离该树权值最⼩且不在树中的顶点，加⼊到⽣成树中。然后更新与该点相连的点到⽣成树的最短距离；
3. 重复2操作n次，直到所有顶点都加⼊为⽌
   

11 - 51 - 5 - 21 - 5 - 2
1 - 41 - 5 - 2 - 3
1 - 4

P3366 【模板】最小生成树 - 洛谷

代码实现-邻接矩阵：

#include <bits/stdc++.h>
using namespace std;const int N = 5010, INF = 0x3f3f3f3f;int n, m;
int edges[N][N]; //邻接矩阵int dist[N]; //某个点距离生成树的最短距离
bool st[N]; //标记哪些点已经加入到生成树int prim()
{//初始化memset(dist, 0x3f, sizeof dist);dist[1] = 0;int ret = 0;for (int i = 1; i <= n; i++) //循环加入n个点{//1.找最近点int t = 0;for (int j = 1; j <= n; j++)if (!st[j] && dist[j] < dist[t])t = j;//判断是否连通if (dist[t] == INF) return INF;st[t] = true;ret += dist[t];//2.更新距离for (int j = 1; j <= n; j++) //枚举t能走到哪{dist[j] = min(dist[j], edges[t][j]);}}return ret;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;//初始化为无穷memset(edges, 0x3f, sizeof edges);for (int i = 1; i <= m; i++){int x, y, z; cin >> x >> y >> z;//有重边求最小值edges[x][y] = edges[y][x] = min(edges[x][y], z);}int ret = prim();if (ret == INF) cout << "orz" << endl;else cout << ret << endl;return 0;
}

代码实现-邻接表-vector数组：

#include <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;const int N = 5010, INF = 0x3f3f3f3f;int n, m;
vector<PII> edges[N];int dist[N];
bool st[N];int prim()
{memset (dist, 0x3f, sizeof dist);dist[1] = 0;int ret = 0;for (int i = 1; i <= n; i++){//1.找最近点int t = 0;for (int j = 1; j <= n; j++)if (!st[j] && dist[j] < dist[t])t = j;//判断是否连通if (dist[t] == INF) return INF;st[t] = true;ret += dist[t];//2.更新距离for (auto& p : edges[t]){int a = p.first, b = p.second;//t->a,权值是bdist[a] = min(dist[a], b);}}return  ret;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++){int x, y, z; cin >> x >> y >> z;edges[x].push_back({y,z});edges[y].push_back({x,z});}int ret = prim();if (ret == INF) cout << "orz" << endl;else cout << ret << endl;return 0;
}

Kruskal算法

核⼼：不断加边。
Kruskal 算法构造最⼩⽣成树的基本思想：

1. 所有边按照权值排序；
2. 每次选出权值最⼩且两端顶点不连通的⼀条边，直到所有顶点都联通
   

1 - 51 - 5 - 21 - 5 - 2
1 - 41 - 5 - 2 - 3
1 - 4

#include <bits/stdc++.h>
using namespace std;const int N = 5010, M = 2e5 + 10, INF = 0x3f3f3f3f;int n, m;
struct node
{int x, y, z;
}a[M];int fa[N]; //并查集bool cmp(node& a, node& b)
{return a.z < b.z;
}int find(int x)
{return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
}int kk()
{sort (a+1, a+1+m, cmp);int cnt = 0;int ret = 0;for (int i = 1; i <= m; i++){int x = a[i].x, y = a[i].y, z = a[i].z;int fx = find(x), fy = find(y);if (fx != fy){cnt++;ret += z;fa[fx] = fy;}}return cnt == n-1 ? ret : INF;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++) cin >> a[i].x >> a[i].y >> a[i].z;//初始化并查集for (int i = 1; i <= n; i++) fa[i] = i;int ret = kk();if (ret == INF) cout << "orz" << endl;else cout << ret << endl;return 0;
}

P1194 买礼物 - 洛谷

题⽬转化：

• 如果把每⼀个零⻝看成⼀个节点，优惠看成⼀条边，就变成在图中找最⼩⽣成树的问题。
• 因此，跑⼀遍kk算法即可。
  注意：

1. 存边的时候，没有必要存重复的，并且权值过⼤的也不需要存；
2. 最终提取结果的时候，虽然有可能构造不出来⼀棵最⼩⽣成树，但是要在已有的构造情况下处理结果

#include <bits/stdc++.h>
using namespace std;const int N = 500 * 500 + 10;int a, n;int pos;
struct node
{int x, y, z;
}e[N];int fa[N];int find (int x)
{return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}int cnt, ret;bool cmp(node& a, node& b)
{return a.z < b.z;
}void kk()
{sort(e+1, e+1+pos, cmp);for (int i = 1; i <= pos; i++){int x = e[i].x, y = e[i].y, z = e[i].z;int fx = find(x), fy = find(y);if (fx != fy){cnt++;ret += z;fa[fx] = fy;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> a >> n;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){int k; cin >> k;if (i >= j || k > a || k == 0) continue;pos++;e[pos].x = i; e[pos].y = j; e[pos].z = k;}for (int i = 1; i <= n; i++) fa[i] = i;kk();cout << ret + (n - cnt) * a << endl;return 0;
}

P2330 [SCOI2005] 繁忙的都市 - 洛谷

定理：最⼩⽣成树就是瓶颈⽣成树。
在kk算法中，维护边权的最⼤值即可

#include <bits/stdc++.h>
using namespace std;const int N = 310, M = 8010;int n, m;
struct node
{int x, y, z;
}e[M];int fa[N];int find (int x)
{return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}int ret; //最大边的权值bool cmp(node& x, node& y)
{return x.z < y.z;
}void kk()
{for (int i = 1; i <= n; i++) fa[i] = i;sort(e+1, e+1+m, cmp);for (int i = 1; i <= m; i++){int x = e[i].x, y = e[i].y, z = e[i].z;int fx = find(x), fy = find(y);if (fx != fy){ret = max(ret, z);fa[fx] = fy;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++) cin >> e[i].x >> e[i].y >> e[i].z;cout << n - 1 << " ";kk();cout << ret << endl;return 0;
}

P2573 [SCOI2012] 滑雪 - 洛谷

第⼀问：从起点开始，做⼀次dfs/bfs就可以扫描到所有的点。
第⼆问：因为有回溯的效果，相当于就是选择⼀些边，把所有的点都连接起来。但是需要注意：

• 由于这些边是有⽅向的，我们只要保证能从1位置出发，访问到所有的点即可。与最⼩⽣成树还是有差异的。
• 为了能保证选出来的边能够从1访问所有点，应该优先考虑去往更⾼位置的边，这样才能向下⾛到更低的位置

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
typedef pair<int, int> PII;const int N = 1e5 + 10, M = 2e6 + 10;int n, m;
int h[N];vector<PII> edges[N];int fa[N];int find(int x)
{return fa[x] == x ? x : fa[x] = find(fa[x]);
}LL cnt, ret;
bool st[N];int pos;
struct node
{int x, y, z;  
}e[M];void dfs(int u)
{cnt++;st[u] = true;for (auto& p : edges[u]){int v = p.first, k = p.second;pos++;e[pos].x = u; e[pos].y = v; e[pos].z = k;if (!st[v]) dfs(v);}
}bool cmp(node& a, node& b)
{int y1 = a.y, z1 = a.z, y2 = b.y, z2 = b.z;if (h[y1] != h[y2]) return h[y1] > h[y2];else return z1 < z2;
}void kk()
{for (int i = 1; i <= n; i++) fa[i] = i;sort (e+1, e+1+pos, cmp);for (int i = 1; i <= pos; i++){int x = e[i].x, y = e[i].y, z = e[i].z;int fx = find(x), fy = find(y);if (fx != fy){ret += z;fa[fx] = fy;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> h[i];for (int i = 1; i <= m; i++){int x, y, z; cin >> x >> y >> z;    if (h[x] >= h[y]) edges[x].push_back({y, z});if (h[x] <= h[y]) edges[y].push_back({x, z});}dfs(1);cout << cnt << " ";kk();cout << ret << endl;return 0;
}