Acwing:严格次小生成树(求两点间路径上最大边的权值)(模板)
洛谷:严格次小生成树
-
求两点间路径上最大边的权值,就不能通过前缀和了,会丢失信息。每个结点存到其他结点的路径最大边权又占用过多空间
O
(
n
2
)
O(n^2)
O(n2)
-
因此学习下倍增优化存点的思想,将这空间二进制压缩成
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)
-
维护一个
d
[
i
]
[
j
]
d[i][j]
d[i][j] ,维护从 i 点往上跳
2
j
2^j
2j 步这条路径上的最大边权
-
如果是求
严
格
次
小
树
严格次小树
严格次小树 那就要维护一个
最
大
最大
最大 d1 和一个
次
大
次大
次大 d2 数组。最后 lca 求最近公共祖先时,随时记录每一条路径(二进制压缩过,但累计在一起信息不会丢失),就能得出两点间路径的最大和次大边权了
代码:
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define ul u << 1
#define ur u << 1 | 1
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100010, M = N << 1, MM = 3000010;
int INF = 0x3f3f3f3f, mod = 100003;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D;
int h[N], e[M], ne[M], w[M], idx;
int p[N], dep[N], q[N];
int fa[N][17], d1[N][17], d2[N][17];
struct edge
{
int l, r, w;
bool tree;
bool operator <(const edge& t)const {
return w < t.w;
}
}ed[N * 3];
void add(int a, int b, int x) {
e[idx] = b, w[idx] = x, ne[idx] = h[a], h[a] = idx++;
}
int find(int x) {
if (p[x] != x)p[x] = find(p[x]);
return p[x];
}
ll kruskal() {
mem(h, -1);
sort(ed, ed + m);
for (int i = 1; i <= n; i++)p[i] = i;
ll res = 0;
for (int i = 0; i < m; i++) {
int a = ed[i].l, b = ed[i].r, w = ed[i].w;
int fa = find(a), fb = find(b);
if (fa != fb) {
res += w;
ed[i].tree = true;
add(a, b, w), add(b, a, w);
p[fa] = fb;
}
}
return res;
}
void bfs() {
mem(dep, 0x3f);
dep[0] = 0, dep[1] = 1;
int hh = 0, tt = 0;
q[tt++] = 1;
while (hh < tt)
{
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dep[j] > dep[t] + 1) {
dep[j] = dep[t] + 1;
q[tt++] = j;
fa[j][0] = t;
d1[j][0] = w[i], d2[j][0] = -INF;
for (int k = 1; k <= 16; k++) {
int anc = fa[j][k - 1];
fa[j][k] = fa[anc][k - 1];
int dist[] = { d1[j][k - 1],d2[j][k - 1],d1[anc][k - 1],d2[anc][k - 1] };
d1[j][k] = d2[j][k] = -INF;
for (int u = 0; u < 4; u++) {
int d = dist[u];
if (d > d1[j][k])d2[j][k] = d1[j][k], d1[j][k] = d;
else if (d != d1[j][k] && d > d2[j][k])d2[j][k] = d;
}
}
}
}
}
}
int lca(int a, int b, int x) {
int distan[N * 2];
int cnt = 0;
if (dep[a] < dep[b])swap(a, b);
for (int j = 16; j >= 0; j--)
if (dep[fa[a][j]] >= dep[b]) {
distan[cnt++] = d1[a][j];
distan[cnt++] = d2[a][j];
a = fa[a][j];
}
if (a != b) {
for (int j = 16; j >= 0; j--)
if (fa[a][j] != fa[b][j]) {
distan[cnt++] = d1[a][j];
distan[cnt++] = d2[a][j];
distan[cnt++] = d1[b][j];
distan[cnt++] = d2[b][j];
a = fa[a][j], b = fa[b][j];
}
distan[cnt++] = d1[a][0];
distan[cnt++] = d1[b][0];
}
int dist1 = -INF, dist2 = -INF;
for (int i = 0; i < cnt; i++) {
int d = distan[i];
if (d > dist1)dist2 = dist1, dist1 = d;
else if (d != dist1 && d > dist2)dist2 = d;
}
if (x > dist1)return x - dist1;
if (x > dist2)return x - dist2;
return INF;
}
int main() {
cinios;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, x;
cin >> a >> b >> x;
ed[i] = { a,b,x };
}
ll sum = kruskal();
bfs();
ll ans = LNF;
for (int i = 0; i < m; i++) {
if (!ed[i].tree) {
int a = ed[i].l, b = ed[i].r, w = ed[i].w;
ans = min(ans, sum + lca(a, b, w));
}
}
cout << ans;
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)