算法笔记--次小生成树次短路 k 短路

1.次小生成树

非严格次小生成树：边权和小于等于最小生成树的边权和

严格次小生成树：边权和小于最小生成树的边权和

算法：先建好最小生成树，然后对于每条不在最小生成树上的边（u，v，w）如果我们把它放到最小生成树中，会形成一个环，那么再从这个环上删除一个除加进去的边外且小于（或等于）当前w的最大权值边，可以用倍增（或树剖）维护链上的最大值来实现非严格的，对于严格的来说，最大值可能等于w，那么就再维护一个次大值。

P4180 【模板】严格次小生成树[BJWC2010]

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head

const int N = 1e5 + 10, M = 3e5 + 10;
const int INF = 0x3f3f3f3f;
pair<int, pii> e[M];
vector<pii> g[N];
int fa[N], deep[N], anc[N][20];
pii mx[N][20];
bool vis[M];
void init(int n) {
    for (int i = 0; i <= n; ++i) fa[i] = i;
}
int Find(int x) {
    if(x == fa[x]) return x;
    else return fa[x] = Find(fa[x]);
}
pii MX(pii a, pii b) {
    pii res = {-INF, -INF};
    if(a.fi > b.fi) res.fi = a.fi, res.se = b.fi;
    else if(a.fi < b.fi) res.fi = b.fi, res.se = a.fi;
    else res.fi = a.fi;
    res.se = max(res.se, a.se);
    res.se = max(res.se, b.se);
    return res;
}
void dfs(int u, int o, int w) {
    deep[u] = deep[o] + 1;
    if(u != 1) {
        anc[u][0] = o;
        for (int i = 1; i < 20; ++i) anc[u][i] = anc[anc[u][i-1]][i-1];
        mx[u][0] = {w, -INF};
        for (int i = 1; i < 20; ++i) mx[u][i] = MX(mx[u][i-1], mx[anc[u][i-1]][i-1]);
    }
    else {
        for (int i = 0; i < 20; ++i) anc[u][i] = o;
        for (int i = 0; i < 20; ++i) mx[o][i] = mx[u][i] = {-INF, -INF};
    }
    for (pii p : g[u]) {
        int v = p.fi;
        int w = p.se;
        if(v != o) {
            dfs(v, u, w);
        }
    }
}
int lca(int u, int v) {
    if(deep[u] < deep[v]) swap(u, v);
    for (int i = 19; i >= 0; --i) if(deep[anc[u][i]] >= deep[v]) u = anc[u][i];
    if(u == v) return u;
    for (int i = 19; i >= 0; --i) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
    return anc[u][0];
}
int main() {
    int n, m;
    LL tot = 0;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) scanf("%d %d %d", &e[i].se.fi, &e[i].se.se, &e[i].fi);
    init(n);
    sort(e+1, e+1+m);
    for (int i = 1; i <= m; ++i) {
        int x = Find(e[i].se.fi);
        int y = Find(e[i].se.se);
        if(x == y) vis[i] = true;
        else fa[x] = y, g[e[i].se.fi].pb({e[i].se.se, e[i].fi}), g[e[i].se.se].pb({e[i].se.fi, e[i].fi}), tot += e[i].fi;
    }
    dfs(1, 0, 0);
    LL ans = LONG_MAX;
    for (int i = 1; i <= m; ++i) {
        if(vis[i]) {
            int u = e[i].se.fi;
            int v = e[i].se.se;
            int l = lca(u, v);
            pii mm = {-INF, -INF};
            for (int i = 19; i >= 0; i--) if(deep[anc[u][i]] >= deep[l]) mm = MX(mm, mx[u][i]), u = anc[u][i];
            ;
            for (int i = 19; i >= 0; i--) if(deep[anc[v][i]] >= deep[l]) mm = MX(mm, mx[v][i]), v = anc[v][i] ;
            if(mm.fi < e[i].fi) ans = min(ans, e[i].fi + tot - mm.fi);
            else if(mm.se < e[i].fi && mm.se != -INF)ans = min(ans, e[i].fi + tot - mm.se);
        }
    }
    printf("%lld\n", ans);
    return 0;
}

2.次短路

次短路：到某个点的距离比最短路距离大的距离

参照挑战程序设计竞赛P108

到某个点v的次短路要么是其他某个顶点u的最短路再加上u -> v的边，要么是到u的次短路再加上u -> v的边，于是考虑Dijkstra算法更新最短路和次短路。

POJ 3225

代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
#define y1 y11
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define pdd pair<double, double>
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(x) cerr << #x << " = " << x << "\n";
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//head

const int N = 5e3 + 10;
vector<pii> g[N];
int d[N], dd[N];
priority_queue<pii, vector<pii>, greater<pii> > q;
int main() {
    int n, m, u, v, w;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d %d", &u, &v, &w);
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    mem(d, 0x7f);
    mem(dd, 0x7f); 
    d[1] = 0; //dd[1]不能等于0,n=1且自环的情况 
    q.push({0, 1});
    while(!q.empty()) {
        pii p = q.top();
        q.pop();
        int u = p.se;
        if(dd[u] < p.fi) continue;
        for (int i = 0; i < g[u].size(); ++i) {
            int v = g[u][i].fi;
            int w = g[u][i].se;
            int d1 = p.fi + w;
            if(d1 < d[v]) {
                swap(d1, d[v]);
                q.push({d[v], v});
            }
            if(d1 < dd[v] && d1 > d[v]) {
                dd[v] = d1;
                q.push({dd[v], v});
            }
        }
    }
    printf("%d\n", dd[n]);
    return 0;
}