1.次小生成树
非严格次小生成树：边权和小于等于最小生成树的边权和
严格次小生成树： 边权和小于最小生成树的边权和
算法：先建好最小生成树，然后对于每条不在最小生成树上的边（u，v，w）如果我们把它放到最小生成树中，会形成一个环，那么再从这个环上删除一个除加进去的边外且小于（或等于）当前w的最大权值边，可以用倍增（或树剖）维护链上的最大值来实现非严格的，对于严格的来说，最大值可能等于w，那么就再维护一个次大值。
代码：
#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 << " "; #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 ", ans); return 0; }
2.次短路
次短路：到某个点的距离比最短路距离大的距离
参照挑战程序设计竞赛P108
到某个点v的次短路要么是其他某个顶点u的最短路再加上u -> v的边，要么是到u的次短路再加上u -> v的边，于是考虑Dijkstra算法更新最短路和次短路。
代码：
#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 << " "; #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 ", dd[n]); return 0; }
ps:最短路记数也可以用Dijkstra,考虑松弛时如果d[v] > d[u] + w, 那么cnt[v] = cnt[u], 如果d[v] == d[u] + w, 那么cnt[v] += cnt[u]。
3.k短路
A* 或者 可持久化堆
都不会，未完待续。。。