严格次小生成树

次小生成树

即不等于最小生成树的生成树的值的最小值

方法是考虑每条不在最小生成树上的边，连上这条边以后会在树上形成一个环，我们需要在这个环上找一个不等于刚连起来的边的最大值，然后删掉它

这里用的是倍增LCA来维护树上链的最大值和次大值

我们需要先跑出一个最小生成树，然后建好图，在图上跑dfs，dfs先更新ff[i][j]数组,和maxn1[i][j]和maxn2[i][j],方法就是用的倍增，然后再去遍历该点连接的其他点

跑完dfs后，再写一个求lca的函数，以及一个计算树的路径上的最大值的函数，根据的就是我们的倍增来写

最后枚举每条不在最小生成树上的边即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,ll> pii;

#define MAX 300000 + 50
int n, m, k, x;
struct ran{
    int x, y;
    ll z;
    bool operator < (const ran &a)const{
        return z < a.z;
    }
}tr[MAX];

vector<pii>G[MAX];
ll MST;
int fa[MAX];
bool vis[MAX];
int getfa(int x){
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
void kruskal(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> tr[i].x >> tr[i].y >> tr[i].z;
    }
    sort(tr + 1, tr + 1 + m);
    for(int i = 1; i <= n; ++i)fa[i] = i;
    for(int i = 1; i <= m; ++i){
        int xx = getfa(tr[i].x);
        int yy = getfa(tr[i].y);
        if(xx != yy){
            vis[i] = 1;
            G[tr[i].x].push_back(m_p(tr[i].y, tr[i].z));
            G[tr[i].y].push_back(m_p(tr[i].x, tr[i].z));
            MST += tr[i].z;
            fa[xx] = yy;
        }
    }
}

ll maxn1[MAX][22];
ll maxn2[MAX][22];
int deep[MAX];
int ff[MAX][22];
void dfs(int u, int fa){
    for(int i = 1; i <= 20; ++i){
        ff[u][i] = ff[ff[u][i - 1]][i - 1];
        maxn1[u][i] = max(maxn1[ff[u][i - 1]][i - 1], maxn1[u][i - 1]);
        maxn2[u][i] = max(maxn2[u][i - 1], maxn2[ff[u][i - 1]][i - 1]);
        if(maxn1[u][i - 1] > maxn1[ff[u][i - 1]][i - 1])maxn2[u][i] = maxn1[ff[u][i - 1]][i - 1];
        else if(maxn1[u][i - 1] < maxn1[ff[u][i - 1]][i - 1])maxn2[u][i] = maxn1[u][i - 1];
    }
    for(auto [v, d] : G[u]){
        if(v == fa)continue;
        deep[v] = deep[u] + 1;
        maxn1[v][0] = d;
        maxn2[v][0] = 0;
        ff[v][0] = u;
        dfs(v, u);
    }
}

int lca(int x, int y){
    if(deep[x] < deep[y])swap(x, y);
    for(int i = 20; i >= 0; --i){
        if(deep[ff[x][i]] >= deep[y])x = ff[x][i];
    }
    if(x == y)return x;
    for(int i = 20; i >= 0; --i){
        if(ff[x][i] != ff[y][i]){
            x = ff[x][i];
            y = ff[y][i];
        }
    }
    return ff[x][0];
}

ll cal(int x, int y, ll z){
    ll ans = -1e18;//一定要设成-1e18，不然会挂在自环上
    for(int i = 20; i >= 0; --i){
        if(deep[ff[x][i]] >= deep[y]){
            if(z == maxn1[x][i])ans = max(ans, maxn2[x][i]);
            else ans = max(ans, maxn1[x][i]);
            x = ff[x][i];
        }
    }
    return ans;
}

void work(){
    kruskal();
    deep[1] = 1;
    ff[1][0] = 0;
    maxn1[1][0] = 0;
    maxn2[1][0] = 0;
    dfs(1, 0);
    ll _MST = 1e18;
    for(int i = 1; i <= m; ++i){
        if(!vis[i]){
            int root = lca(tr[i].x, tr[i].y);
            ll xx = cal(tr[i].x, root, tr[i].z);
            ll yy = cal(tr[i].y, root, tr[i].z);
            _MST = min(_MST, MST - max(xx, yy) + tr[i].z);
        }
    }
    cout << _MST << endl;
}


int main(){
    io;
    work();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126