知识总结
最小生成树
- 最小生成树的定义：在一个无向连通图中，找出权值最小的生成树，使得生成树中任意两个顶点间都有且仅有一条路径。
- 最小生成树的性质：
- 无向连通图的最小生成树是唯一的。
- 最小生成树的权值是图中所有边的权值的最小值。
- 最小生成树的边数等于图的顶点数减一。
- 最小生成树的边权值之和等于图的边权值之和。
- 最小生成树的算法：
- Prim算法：每次选择权值最小的边加入生成树，直到生成树的边数等于图的顶点数减一。
- Kruskal算法：每次选择权值最小的边加入生成树，直到生成树的边数等于图的边数。
kruskal 重构树
- 根据 kruskal 算法的思想
- kruskal 重构树的叶子节点为原图中的点，其他店为虚点，点权为原图中的边权
- 建 kruskal 重构树，维护每个子树的根到子树内的最短路，倍增查询满足条件的最小答案
题目
T1 电话连线(dial)
题目描述
一个国家有 n 个城市。若干个城市之间有电话线连接，现在要增加 m 条电话线，使得任意两个城市之间都直接或间接经过其他城市有电话线连接，你的程序应该能够找出最小费用及其一种连接方案。
思路解析
本题是一道很明显的最小生成树，原本是零的边保留下来，那么在做最小生成树的时候必定会将本来就有的边先用掉。当然也可以事先处理处联通块，更新图后进行最小生成树，至于使用克鲁斯科尔还是prim就随意了.两者复杂度分别是 $O(nnlognn)$ $O(n*nlogn)
代码实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e18, N = 1e3+10;
int n, ans, dis[N], mp[N][N], f[N][2], to[N];
bool vis[N];
void prim() {
int minx, k = 1, tot = 0, cnt = 0;
fill(dis, dis + N, inf);
dis[1] = 0;
for (int i = 1; i <= n; i++) {
minx = inf;
for (int j = 1; j <= n; j++) {
if (dis[j] < minx && !vis[j]) {
k = j;
minx = dis[j];
}
}
ans += minx;
vis[k] = true;
for (int j = 1; j <= n; j++) {
if (mp[k][j] < dis[j] && !vis[j]) {
dis[j] = mp[k][j];
to[j] = k;
}
}
if (minx) {
f[cnt][0] = min(to[k], k);
f[cnt][1] = max(to[k], k);
cnt++;
}
}
printf("%lld\n%lld", cnt, ans);
return;
}
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%lld", &mp[i][j]);
}
}
prim();
return 0;
}
T2 安慰奶牛
题目描述
https://www.luogu.com.cn/problem/U183932
思路解析
考虑每条边都必须经过两次，转换每条边的边权为边权*2+两边的点权，跑一个最小生成树
代码实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e6 + 5, M = 2e6 + 10, inf = LONG_LONG_MAX;
struct node {
int u, v, w;
} e[M];
bool operator<(const node& x, const node& y) {
return x.w < y.w;
}
int n, m, father[N], c[N], minn = inf, ans, num_edge;
int findfather(int v) {
if (father[v] == v)
return v;
else {
father[v] = findfather(father[v]);
return father[v];
}
}
void Kruskal() {
for (int i = 1; i <= n; i++) {
father[i] = i;
}
sort(e + 1, e + 1 + m);
for (int i = 1; i <= m; i++) {
int fu = findfather(e[i].u), fv = findfather(e[i].v);
if (fu != fv) {
ans += e[i].w;
father[fu] = fv;
num_edge++;
if (num_edge == n - 1)
break;
}
}
return;
}
signed main() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &c[i]);
minn = min(c[i], minn);
}
ans = minn;
for (int i = 1; i <= m; i++) {
scanf("%lld%lld%lld", &e[i].u, &e[i].v, &e[i].w);
e[i].w = 2 * e[i].w + c[e[i].u] + c[e[i].v];
}
Kruskal();
printf("%lld\n", ans);
return 0;
}
T3 新的开始
题目描述
发展采矿业当然首先得有矿井， 小FF花了上次探险获得的千分之一的财富请人在岛上挖了n口矿井， 但他似乎忘记考虑的矿井供电问题……
为了保证电力的供应， 小FF想到了两种办法：
1、 在这一口矿井上建立一个发电站， 费用为v（发电站的输出功率可以供给任意多个矿井）。
2、 将这口矿井与另外的已经有电力供应的矿井之间建立电网， 费用为p。
小FF希望身为”NewBe_One" 计划首席工程师的你帮他想出一个保证所有矿井电力供应的最小花费。
思路解析
井建一个新点，每个点可以选择向井连边或者点与点之间连边，边权不同，求一个最小生成树即可
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 310
int n, m, i, j, k;
int v[N], b[N], a[N], p[N][N], ans;
signed main() {
scanf("%lld", &n);
a[k = 0] = 1e9;
for (i = 1; i <= n; ++i) {
scanf("%lld", &v[i]);
a[i] = v[i];
}
for (i = 1; i <= n; ++i) {
for (j = 1; j <= n; ++j) {
scanf("%lld", &p[i][j]);
}
}
for (i = 1; i <= n; ++i) {
for (j = 1, k = 0; j <= n; ++j)
if (!b[j] && a[j] < a[k])
k = j;
for (j = b[k] = 1, ans += a[k]; j <= n; ++j)
if (!b[j])
a[j] = min(a[j], p[k][j]);
}
printf("%lld", ans);
return 0;
}
T4 过路费
题目描述
在某个遥远的国家里，有n个城市。编号为1,2,3,…,n。这个国家的政府修建了m条双向道路，每条道路连接着两个城市。政府规定从城市S到城市T需要收取的过路费为所经过城市之间道路长度的最大值。如：A到B长度为2，B到C长度为3，那么开车从A经过B到C需要上交的过路费为3。
佳佳是个做生意的人，需要经常开车从任意一个城市到另外一个城市，因此他需要频繁地上交过路费，由于忙于做生意，所以他无时间来寻找交过路费最低的行驶路线。然而，当他交的过路费越多他的心情就变得越糟糕。作为秘书的你，需要每次根据老板的起止城市，提供给他从开始城市到达目的城市，最少需要上交多少过路费。
思路解析
考虑最小生成树。
然后转换成 LCA 问题。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int f[N][21], g[N][21], dep[N], fa[N];
vector<pair<int, int> > e[N];
struct Edge {
int u, v, w;
} eg[N];
bool cmp(Edge a, Edge b) {
return a.w < b.w;
}
void addEdge(int x, int y, int z) {
e[x].push_back(make_pair(y, z));
e[y].push_back(make_pair(x, z));
}
int union_find(int x) {
return fa[x] < 0 ? x : fa[x] = union_find(fa[x]);
}
void Kruskal(int n, int m) {
for (int i = 1; i <= n; ++i) {
fa[i] = -1;
}
sort(eg + 1, eg + m + 1, cmp);
for (int i = 1, x, y; i <= m; ++i) {
if ((x = union_find(eg[i].u)) != (y = union_find(eg[i].v))) {
if (fa[x] <= fa[y])
fa[x] += fa[y], fa[y] = x;
else
fa[y] += fa[x], fa[x] = y;
addEdge(eg[i].u, eg[i].v, eg[i].w);
}
}
}
void dfs(int x, int fa) {
f[x][0] = fa;
for (int j = 0; f[x][j]; ++j)
f[x][j + 1] = f[f[x][j]][j], g[x][j + 1] = max(g[x][j], g[f[x][j]][j]);
for (auto v : e[x])
if (v.first != fa)
dep[v.first] = dep[x] + 1, g[v.first][0] = v.second, dfs(v.first, x);
}
int query(int x, int y) {
int ans = 0;
if (dep[x] < dep[y]) {
int t = x;
x = y;
y = t;
}
for (int i = 0, d = dep[x] - dep[y]; i <= 20; ++i)
if (d & (1 << i))
ans = max(ans, g[x][i]), x = f[x][i];
if (x == y)
return ans;
for (int i = 20; i >= 0; --i)
if (f[x][i] != f[y][i])
ans = max(ans, max(g[x][i], g[y][i])), x = f[x][i], y = f[y][i];
ans = max(ans, max(g[x][0], g[y][0]));
return ans;
}
int main() {
int n, m, q;
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i)
scanf("%d %d %d", &eg[i].u, &eg[i].v, &eg[i].w);
Kruskal(n, m);
dfs(1, 0);
scanf("%d", &q);
for (int i = 1, x, y; i <= q; ++i) {
scanf("%d %d", &x, &y);
printf("%d\n", query(x, y));
}
return 0;
}
T5 公路网问题
题目描述
某省的公路网有一个简单的结构：以省会城市为起点，道路延伸到邻近的一些城市，从这些城市开始，又有一些道路扩展到次近城市，依此类推，因此，各城市可以被视为按"层次"环绕在省会城市周围的。第i层的城市只可能与第i-1层和第i+1层中的城市直接相连（省会城市被视为第0层 ）。公路网中不会出现回路。任何第i层的城市只与i-1层的一个城市直接相连，但是可以与0到多个第i+1层的城市直接相连。因此，从一个指定的第i层的城市到省会城市，游客只需简单地顺唯一的一条路到达与它直接相连的第i－1层的城市，并重复这一步骤，这样每一步后都将更加接近省会城市，直至最后到达。
对于一个给定的公路城市网，你的任务是找出给定两城市之间的最短通路，路径长度用中途经过的城市的数目衡量。
思路解析
很容易看出这是一棵树.
我们要求的就是树上的路径.
定义H[i]表示i的深度
假设是i点走到j点
可以很容易的想到,凡是H[i]>H[j]的时候,肯定我们先移动i不会有错误,反之依然.
当h[i] == h[j]的时候,我们将两个点同时上伸也不会有错.
所以这就是一个O(N)的模拟了.
代码实现
#include <iostream>
#include <map>
#include <queue>
#include <stack>
using namespace std;
int n, Q, ans, LCA, num, cnt, Fa[100001], deep[100001]; // Fa表示某城市的父亲城市（省会为根城市），deep表示某城市的深度
vector<int> V[100001]; // 存树用
map<string, int> mp1; // 将某城市映射为一个数用
map<int, string> mp2; // 将某城市映射为的那个数从新映射回某城市用
queue<int> num1; // 输出用
stack<int> num2; // 输出用
void Deep(int now, int fa) // 计算节点深度
{
Fa[now] = fa;
deep[now] = deep[fa] + 1;
for (int i = 0; i < V[now].size(); i++)
if (V[now][i] != fa)
Deep(V[now][i], now);
}
int lca(int x, int y) // 向上标记法求lca
{
if (deep[x] > deep[y])
swap(x, y);
while (deep[x] != deep[y])
y = Fa[y];
while (x != y) {
x = Fa[x];
y = Fa[y];
}
// q.push(mp2[x]);
return x;
}
void do1(int x) {
if (x == LCA) {
num1.push(x);
return;
}
num1.push(x);
do1(Fa[x]);
}
void do2(int x) {
if (x == LCA)
return;
num2.push(x);
do2(Fa[x]);
}
int main() {
cin >> n >> Q;
for (int i = 1; i <= n; i++) {
// 存树
string u, v;
cin >> u >> v;
// 相互转化
if (!mp1[u]) {
mp1[u] = ++cnt;
mp2[cnt] = u;
}
if (!mp1[v]) {
mp1[v] = ++cnt;
mp2[cnt] = v;
}
V[mp1[u]].push_back(mp1[v]);
V[mp1[v]].push_back(mp1[u]);
}
Deep(1, 0); // 计算深度
for (int i = 1; i <= Q; i++) // 求解
{
string x, y;
cin >> x >> y;
// q.push(x);
// q.push(y);
LCA = lca(mp1[x], mp1[y]);
do1(mp1[x]);
do2(mp1[y]);
while (!num1.empty()) {
cout << mp2[num1.front()];
num1.pop();
}
while (!num2.empty()) {
cout << mp2[num2.top()];
num2.pop();
}
cout << ' ';
}
return 0;
}
初赛
