本篇标红的字段均是可以升级的经验条呦~
OJ题来源：洛谷
OJ题名：买礼物
OJ题归属：图论基础【最小生成树】
解题算法：kruskal算法（kk算法）
经验总结：用kurskal算法构造出来的生成树可能有若干个，顶点有不连通的情况不影响他建树，比如：a-a a-a a-a
|
a-a
kruskal算法的关键变量cnt与节点n是有关系的，cnt变量记录选的条数，n是节点个数，n – cnt 的差值就是构建出生成树的具体个数。
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 500 * 500 + 10;
int pos;
int a, n;
int fa[N]; // 并查集
struct node
{
int x, y, z;
}e[N];
int ret, cnt;
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
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()
{
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(); // 求得ret/cnt
cout << ret + (n – cnt) * a << endl;
return 0;
}
OJ题来源：洛谷
OJ题名：繁忙的都市
OJ题归属：图论基础【最小生成树】
解题算法：kruskal算法（kk算法）
此题有三个限制条件，前两个条件翻译出来是要求是一棵生成树，最后一个翻译出来是要是一颗瓶颈生成树。
经验总结：
瓶颈生成树的概念：在所有生成树中，最大边权值最小的生成树。
瓶颈生成树的定理：最小生成树就是瓶颈生成树。
| 最小生成树 | ret维护的是边权和最小 |
| 瓶颈生成树 | ret维护的是 n – 1 条边中，边权最大值 |
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 310, M = 8010;
int n, m;
struct node
{
int x, y, z;
}a[M];
int fa[N]; // 并查集维护已选的顶点
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int ret; // 维护 n – 1 条边中，边权最大值
bool cmp(node& a, node& b)
{
return a.z < b.z;
}
void kk()
{
sort(a + 1, a + 1 + m, cmp);
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)
{
ret = max(ret, z);
fa[fx] = fy;
}
}
}
int main()
{
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;
cout << n – 1 << " ";
kk();
cout << ret << endl;
return 0;
}
OJ题来源：洛谷
OJ题名：滑雪
OJ题归属：图论基础【最小生成树】
解题算法：dfs + kruskal算法（kk算法）
经验总结：最小生成树在概念上是针对于无向图的，但是，这题向我们表明，特殊情景下的有向图也是适用的，这题的图是一个有向图，但是题中提到的时间胶囊的概念，其实功能就是回溯，是的，这样我们就可以把这个有向图可以看成可以递归的二叉树。此题的各个顶点之间不确定是不是连通的，所以不是所有的边都需要记录，我们只记录由1这个节点递归过程中可以经历的边，对这些边进行排序、选边操作。此题kk算法的排序有改变，滑雪滑雪，排序的第一关键字就是高度，由高到低，高度一致时，在按边权由小到大排序。
#include<iostream>
#include<algorithm>
#include<vector>
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> a[N]; // 存图
int fa[N]; // 并查集
int pos; // 在选择范围内的边数
struct node
{
int x, y, z;
}e[M]; // 存储在选择范围内的边
LL cnt, ret; // 景点数 路径和
bool st[N];
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void dfs(int u)
{
cnt++;
st[u] = true;
for (auto& p : a[u])
{
// 存储在选择范围内的边
int y = p.first, z = p.second;
pos++;
e[pos].x = u, e[pos].y = y, e[pos].z = z;
if (!st[y]) dfs(y);
}
}
bool cmp(node& a, node& b)
{
int ay = a.y, by = b.y;
// 排序第一关键字：高度，第二关键字：边权
if (h[ay] != h[by]) return h[ay] > h[by];
else return a.z < b.z;
}
void kk()
{
sort(e + 1, e + 1 + m, 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()
{
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]) a[x].push_back({ y, z });
if (h[y] >= h[x]) a[y].push_back({ x, z });
}
// 并查集初始化
for (int i = 1; i <= n; i++) fa[i] = i;
dfs(1);
cout << cnt << " ";
kk();
cout << ret << endl;
return 0;
}
感谢~
