最小生成树(MST)
在一张n个点m条边的无相图中, 选取一棵树, 边权和最小
Kruskal算法: 适合稀疏图
原理:
贪心, 将排序后的边依次枚举, 选择不成环的边即可.
注意事项:
1. 要排序m条边
2. 并查集要初始化
3. 枚举到m条边
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int p[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
struct Kruskal
{
int a, b, w;
bool operator< (const Kruskal v) const
{
return w < v.w;
}
} g[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
int a, b, w;
for (int i = 0; i < m; i++)
{
cin >> a >> b >> w;
g[i] = {a, b, w};
}
sort(g, g + m);
for (int i = 1; i <= n; i++) p[i] = i;
int res = 0, cnt = 0;
for (int i = 0; i < m; i++)
{
a = g[i].a, b = g[i].b, w = g[i].w;
a = find(a), b = find(b);
if (a != b)
{
p[a] = b;
res += w;
cnt++;
}
}
if (cnt < n - 1) cout << "impossible"; // 图不连通
else cout << res;
return 0;
}
prim算法：适合稠密图
例题:
1. P个点需要P-1条边, 最大的边权尽量小;
2. 卫星电话无视距离, 只有S个l
3. S个卫星电话可以覆盖S-1条边, 那么无线电覆盖P-1-(S-1)条边;
4. 将P个哨所两两求直线距离,将边从小到大排序, 选P-S条不成环的边， 最后1条边权即D
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
double a[N], b[N];
int p[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
struct Kruskal
{
int x, y;
double w;
bool operator< (const Kruskal &u) const
{
return w < u.w;
}
} g[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
int cnt = 0;
for (int i = 1; i <= m; i++)
{
cin >> a[i] >> b[i];
for (int j = 1; j < i; j++)
g[cnt++] = {i, j, sqrt((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]))};
}
sort(g, g + cnt);
for (int i = 1; i <= m; i++) p[i] = i;
int k = 0;
for (int i = 0; i < cnt; i++)
{
double w = g[i].w;
int x = g[i].x, y = g[i].y;
x = find(x), y = find(y);
if (x != y)
{
p[y] = x;
k++;
if (k >= m - n)
{
cout << fixed << setprecision(2) << w;
break;
}
}
}
return 0;
}
直接最大生成树就秒了
只要能选出一颗树就一定能把比赛打完
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2010;
ll Cows[N];
int p[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
struct Kruskal
{
ll a, b, w;
bool operator< (const Kruskal &u) const
{
return w > u.w;
}
} g[N * N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> Cows[i];
int cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
g[cnt++] = {i, j, Cows[i] ^ Cows[j]};
sort(g, g + cnt);
for (int i = 1; i <= n; i++) p[i] = i;
ll res = 0, k = 0;
for (int i = 0; i < cnt; i++)
{
int a = g[i].a, b = g[i].b, w = g[i].w;
a = find(a), b = find(b);
if (a != b)
{
p[b] = a;
res += w;
k++;
}
if (k >= n - 1) break;
}
cout << res;
return 0;
}
构造一个虚拟点（超级发电站）把点权转化为边权 就会发现这是一个板子题(我们这个包含了 超级发电站 的图通电之后, 必定是连通的, 最小费用就是这张图中的最小生成树, 用 Kruskal 算法跑就行了)
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int p[N];
int P[N][N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
struct Kruskal
{
int a, b, w;
bool operator< (const Kruskal &u) const
{
return w < u.w;
}
} g[N * N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
int cnt = 0;
for (int i = 1, w; i <= n; i++)
{
cin >> w;
g[cnt++] = {n + 1, i, w};
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) cin >> P[i][j];
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
g[cnt++] = {i, j, P[i][j]};
for (int i = 1; i <= n + 1; i++) p[i] = i;
sort(g, g + cnt);
int res = 0;
for (int i = 0; i < cnt; i++)
{
int a = g[i].a, b = g[i].b, w = g[i].w;
a = find(a), b = find(b);
if (a != b)
{
p[b] = a;
res += w;
}
}
cout << res;
return 0;
}
方法1 暴力枚举点对 50%
时间复杂度 $O(N•N•logN)$
1. 枚举没有连边的点对x和y, 边权设为树上x到y的路径上的最大边权w+1;
2. 倍增维护f[i][j]表示点i向上走2^j步区间内的最大边权
方法2: 最小生成树+乘法原理 100%
时间复杂度 $O(N•logN)$
1. T中的树边将2个连通块链接, 但是树边不能被替换;
2. 两个连通块中的点对要连边, 权值设为W+1, 其中W是树边的边权;
3. 两个连通块连边的贡献为(s[find(x)] * s[find(y)] - 1) * (w + 1);
4. 对于n-1条树边, 重复执行1~3, 将贡献累加, 并加上T的比边权和即为答案
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10;
ll p[N], s[N];
ll find(ll x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
struct Kruskal
{
ll a, b, w;
bool operator< (const Kruskal &u) const
{
return w < u.w;
}
} g[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n;
cin >> n;
ll a, b, w;
for (ll i = 1; i < n; i++)
{
cin >> a >> b >> w;
g[i] = {a, b, w};
}
sort(g + 1, g + n);
for (ll i = 1; i <= n; i++) p[i] = i, s[i] = 1;
ll res = 0;
for (ll i = 1; i < n; i++)
{
ll a = g[i].a, b = g[i].b, w = g[i].w;
a = find(a), b = find(b);
res += (s[a] * s[b] - 1) * (w + 1) + w;
a = find(a), b = find(b);
if (a != b)
{
p[a] = b;
s[b] += s[a];
s[a] = 0;
}
}
cout << res;
return 0;
}
时间复杂度 $O(M•N•log(M•N))$
1. 对于m*n个点， 向下和向右连无向边;
2. 将所有的边从小到大排序
3. 每选一条不成环的边, 就会使连通块变大, 首次达到T时， 选取的边
4. 维护连通块内的点数s[x], 以及起始点数st[x]
5. 找到一个合法的连通块时， res += st[find(x)] * w, union(), st[find(x)]=0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 510;
ll A[N][N];
ll p[N * N], s[N * N], st[N * N];
ll m, n, t;
ll get(ll x, ll y)
{
return (x - 1) * n + y;
}
ll find(ll x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
struct Kruskal
{
ll a, b, w;
bool operator< (const Kruskal &u) const
{
return w < u.w;
}
} g[N * N * 2];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> m >> n >> t;
for (ll i = 1; i <= m; i++)
for (ll j = 1; j <= n; j++) cin >> A[i][j];
for (ll i = 1; i <= m; i++)
for (ll j = 1, v; j <= n; j++)
{
cin >> v;
st[get(i, j)] = v;
}
ll cnt = 0;
for (ll i = 1; i <= m; i++)
for (ll j = 1; j <= n; j++)
{
if (i < m)
g[cnt++] = {get(i, j), get(i + 1, j), abs(A[i][j] - A[i + 1][j])};
if (j < n)
g[cnt++] = {get(i, j), get(i, j + 1), abs(A[i][j] - A[i][j + 1])};
}
sort(g, g + cnt);
for (ll i = 1; i <= n * m; i++) p[i] = i, s[i] = 1;
ll res = 0;
for (ll i = 0; i < cnt; i++)
{
ll a = g[i].a, b = g[i].b, w = g[i].w;
a = find(a), b = find(b);
if (a != b)
{
p[a] = b;
s[b] += s[a];
st[b] += st[a];
if (s[b] >= t)
{
res += st[b] * w;
st[b] = 0;
}
}
}
cout << res;
return 0;
}
彩蛋 拓展题目 🎉
FamerJohn:似乎是省选题
题意:给定n个点m条边, 权值为0或1, 求一棵恰好有k条边权为0的生成树
分析:
1. 鹅卵石边分为必选边和非必选边;
2. 将所有不成环的水泥路连边, 若图不连通, 继续选不成环的鹅卵石路, 选中的即为必选边;
3. 再次枚举边, 先将必选边链接, 设共有cnt条, 若cnt>k, 误解, 否则继续选k-cnt条非必选边, 不成环即可;
4. 若k条鹅卵石路选完, 图仍不连通, 继续选不成环的水泥路, 直到连通;
5. 若所有边枚举完, 仍不连通, 无解
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10, M = 1e5 + 10;
int p[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
struct Kruskal
{
int a, b, w, flag;
bool operator< (const Kruskal &u) const
{
return w < u.w;
}
} g[M];
bool cmp(Kruskal a, Kruskal b)
{
if (a.w == b.w) return a.flag > b.flag;
return a.w > b.w;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, k;
cin >> n >> m >> k;
int a, b, w;
for (int i = 0; i < m; i++)
{
cin >> a >> b >> w;
g[i] = {a, b, w ^ 1};
}
for (int i = 1; i <= n; i++) p[i] = i;
sort(g, g + m);
int cnt = 0;
for (int i = 0; i < m; i++)
{
a = g[i].a, b = g[i].b, w = g[i].w;
a = find(a), b = find(b);
if (a != b)
{
p[a] = b;
cnt++;
g[i].flag = w;
}
if (cnt >= n - 1) break;
}
sort(g, g + m, cmp);
for (int i = 1; i <= n; i++) p[i] = i;
cnt = 0;
for (int i = 0; i < m; i++)
{
a = g[i].a, b = g[i].b, w = g[i].flag;
a = find(a), b = find(b);
if (w)
{
p[a] = b;
cnt++, k--;
}
else if (a != b)
{
p[a] = b;
cnt++;
g[i].flag = 1;
if (g[i].w) k--;
if (!k)
while (g[i].w) i++;
}
if (cnt >= n - 1) break;
}
if (k) cout << "no solution";
else
{
for (int i = 0; i < m; i++)
if (g[i].flag) k++;
if (k < n - 1) cout << "no solution";
else
for (int i = 0; i < m; i++)
if (g[i].flag) cout << g[i].a << ' ' << g[i].b << ' ' << (g[i].w ^ 1) << '\n';
}
return 0;
}
