写在前面
最短路部分的代码还是 3 月的，奇丑无比，大家见谅……
最短路
单源最短路径
首先我们介绍一些基本概念。
由于是单源最短路，我们定义一个起点 \(s\)，\(dis_u\) 表示起点 \(s\) 到节点 \(u\) 的最短路长度。
一般来讲，对于一条为 \(w\) 的边 \(u \to v\)，如果目前的最短路是正确的，都应该满足：
\[dis_u+w \geq dis_v \]我们称之为 三角形不等式。
对于不满足三角形不等式的，我们就要更新最短路了：
一条边权为 \(w\) 的边 \(u \to v\)，如果满足 \(dis_u+w<dis_v\)，即可用 \(dis_u+w\) 更新 \(dis_v\)。
这个更新的过程叫做 松弛。
松弛是所有最短路算法的基本操作，我们这里讲的是单源，其实多源也是一样的道理。
Dijkstra
首先是我们的老朋友迪科斯彻。
将有项带权图 \(G=(V,E)\) 的点集 \(V\) 分为两个集合：\(S\) 和 \(T\)，\(S\) 中的点已确定最短路径长度，（即 \(dis_u\) 已更新。起初， \(S\) 中仅包含源点 \(s\)，除 \(dis_s=0\) 外 \(dis\) 初值皆为 \(+\infty\)。）\(T\) 中的点没有确定。
迪科斯彻采用了 贪心 的思想，在 \(S\) 中选择 \(dis_u\) 最小的节点 \(u\)，对 \(u\) 的所有出边进行松弛。
可以证明，由于贪心，每个节点的 \(dis\) 只会更新一次，所以可以对已经松弛所有出边的节点 \(u\) 打标，这个松弛操作 只进行一次 即可。
当然了，最原始的 Dijkstra 时间复杂度还是太假。由于我们只选取最短的一条特殊路径进行松弛，其实可以采用伟大的标准模板库 STL 中的 priority_queue 解决这个问题。
解决之后，我们最坏对 \(m\) 条边进行松弛，优先队列单次操作复杂度 \(O(\log n)\)，所以总复杂度 \(O(m \log n)\)，非常优秀。
接下来是模板题 单源最短路径（标准版） 的 \(Code\)：
#include<bits/stdc++.h>
const int N=1e5+5;
struct Edge { int to,w;
bool operator < (const Edge &a) const {return w>a.w;}
};
std::vector <Edge> E[N];//使用结构体和vector存边
int n,m,s,dis[N];
bool flag[N];
void Dijkstra(int start)
{
memset(dis,0x3f,sizeof dis);
std::priority_queue <Edge> q;
dis[start]=0;
q.push({start,0});
while(!q.empty()){
int u=q.top().to;
q.pop();
if(flag[u]) continue;
/*每个点仅一次作为媒介节点参与松弛。*/
flag[u]=1;
for(auto v:E[u]){
if(dis[u]+v.w<dis[v.to]){
dis[v.to]=dis[u]+v.w;//松弛
q.push({v.to,dis[v.to]});//入集合S
}
}
}
}
int main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0);std::cout.tie(0);
std::cin>>n>>m>>s;
for(int i=1;i<=m;++i){
int u,v,w;
std::cin>>u>>v>>w;
E[u].push_back({v,w});
}
Dijkstra(s);
for(int i=1;i<=n;++i)
std::cout<<dis[i]<<" ";
return 0;
}
但是呢，Dijkstra 不能用于 负环。因为在 Dijkstra 中，每一个顶点作为媒介节点参与松弛操作只有一次，所以得出的结果其实是松弛一次的结果，且无法进行判断其是否是负环。
同时，存在 负边权 的图也 不可 使用 Dijkstra。
Bellman-Ford
其实是一个非常朴素的想法，朴素到其复杂度为 \(O(VE)\)，本质就是对每一条边都尝试松弛。因为其复杂度过于高，实际用途已经基本废了。所以现在主要介绍的是其优化后的算法，SPFA。
SPFA
Shortest Path Faster Algorithm, AKA SPFA。
实际上，这个名字只在大陆存在。因为他实际上叫做 队列优化的 Bellman-Ford 算法。顾名思义，使用队列来优化 Bellman-Ford，本质思想还是朴素的对每个边进行松弛，而且——
\[\text{关于 SPFA, }\textbf{他死了。} \]（ 这个帖子 足见杀他的方法已经发展得很完备了。）
所以直接上 模板题 代码吧。
\(Code\)：
#include<bits/stdc++.h>
const int N=1e4+5;
int n,m,s,dis[N];
bool vis[N];
struct Edge {int to,w;};
std::vector<Edge> E[N];
void SPFA(int start){
std::queue<int> q;
for(int i=1;i<=n;++i)
dis[i]=INT_MAX;
vis[start]=1,dis[start]=0;
q.push(start);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(auto v:E[u]){
if(dis[u]+v.w<dis[v.to]){
dis[v.to]=dis[u]+v.w;
if(!vis[v.to]){
vis[v.to]=1;
q.push(v.to);
}
}
}
}
}
int main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);std::cout.tie(0);
std::cin>>n>>m>>s;
for(int i=1;i<=m;++i){
int u,v,w;
std::cin>>u>>v>>w;
E[u].push_back({v,w});
}
SPFA(s);
for(int i=1;i<=n;++i)
std::cout<<dis[i]<<" ";
return 0;
}
SPFA 的复杂度一般是 \(O(km)\) 的，但是在一些特殊图（如网格图和链套菊花）中会退化到 \(O(nm)\)，所以，慎用。
最后的用武之地 - 判断负环
在 SPFA 中，一个节点最多被松弛 \(n\) 次。所以，我们可以记录每个节点 \(u\) 被松弛的次数 \(sum_u\)，如果出现 \(sum_n>n\)，就可以判定出现负环了。
多源最短路径 - Floyd
OK，现在我们来说一下最后的，多源最短路径。解决他的算法是 Floyd。
其实这个 Floyd 就是一个动态规划，使用邻接矩阵 \(dis(i,j)\) 表示从 \(i\) 到 \(j\) 的最短路径长，枚举每一个节点 \(k\)，判断其是否满足三角形不等式，不满足就 \(dis(i,j) \gets dis(i,k)+dis(k,j)\)。
\(Code:\)
for(int k=1;k<=n;++k){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
dis[i][j]=std::min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
Floyd 是敲着最简单的，但是 \(O(n^3)\) 的复杂度，所以小一点的图哪怕单源也可以凑合用，要是图很大就慎重吧。
生成树
本部分旨在速通，复习用，看细节的朋友可以看 catandcode 的博客。
最小生成树 - MST
性质
就是：
对于一个无向连通图 \(G=(V,E)\)，点集 $U \subsetneq V $ 和 边集 \(A=\{ u \leftrightarrow v|u \in U,v \in (V-U) \} \subsetneq E\)，有无向边 \(u \leftrightarrow v \in A\) 且在 \(A\) 中边权 \(w_{u,v}\) 最小，则这条边必然在该图 \(G\) 的一棵最小生成树中。
Prim
将无向连通图 \(G=(V,E)\) 分为两个集合：已处理 \(A\) 和未处理 \(B\)。处理的过程如下：
- 将一个节点 \(u\) 放入集合 \(A\)；
- 在边集 \(C=\{ i \leftrightarrow j | i \in A,j \in B\}\subset E\) 寻找最小的一条边，将这条边纳入最小生成树；
- 重复第 2 步，直至 \(B= \varnothing\)。
Prim 更适合 稠密图。
\(\text{Code - with Prim by Adjacency List, } 1.19 s \text{ without O2}\)
#include<bits/stdc++.h>
const int MAXN=5005,inf=0x3f3f3f3f;
int n,m,sp[MAXN],dis[MAXN][MAXN];
bool flag[MAXN];
int prim() {
int ans=0,tot=0; sp[0]=inf,flag[1]=1;
for(int i=2;i<=n;++i) sp[i]=dis[1][i];
for(int i=1;i<n;++i) {
int tmp=0;
for(int v=1;v<=n;++v) if(!flag[v] && sp[v]<sp[tmp]) tmp=v;
if(!tmp) break;
ans+=sp[tmp],flag[tmp]=1,++tot;
for(int l=1;l<=n;++l) if(!flag[l] && dis[tmp][l]<sp[l]) sp[l]=dis[tmp][l];
}
return tot==n-1?ans:-1;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
std::cin>>n>>m; memset(dis,0x3f,sizeof dis);
for(int i=1,u,v,w;i<=m;++i) { std::cin>>u>>v>>w; dis[u][v]=dis[v][u]=std::min(dis[u][v],w); }
int ans=prim();
if(~ans) std::cout<<ans<<'\n';
else std::cout<<"orz\n";
return 0;
}
下面是前向星 prim. 与邻接矩阵不同的是，邻接矩阵需要判断重边，\(sp\) 就可以直接赋值；而前向星不需要判断重边，所以 \(sp\) 需要取所有边中的最小值。
\(\text{Code - with Prim by Forward Star, } 474 ms \text{ without O2}\)
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fsp(x) std::fixed<<std::setprecision(x)
#define forE(u) for(int p=head[u],v=E[p].to;p;p=E[p].next,v=E[p].to)
const int N=5005,M=2e5+5,inf=0x3f3f3f3f;
int cnt,head[N];
struct edge { int to,next,w; } E[M<<1];
void add(int u,int v,int w) { E[++cnt].to=v,E[cnt].w=w,E[cnt].next=head[u],head[u]=cnt; }
int n,m,sp[N];
bool flag[N];
int prim() {
memset(sp,0x3f,sizeof sp);
int ans=0,tot=0; flag[1]=1;
forE(1) sp[v]=std::min(sp[v],E[p].w);
for(int i=1;i<=n;++i) {
int tmp=0;
for(int v=1;v<=n;++v) if(!flag[v] && sp[v]<sp[tmp]) tmp=v;
if(sp[tmp]==inf) break;
ans+=sp[tmp],flag[tmp]=1,++tot;
forE(tmp) sp[v]=std::min(sp[v],E[p].w);
}
return tot==n-1?ans:-1;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
std::cin>>n>>m;
for(int i=1,u,v,w;i<=m;++i) { std::cin>>u>>v>>w; add(u,v,w),add(v,u,w); }
int ans=prim();
if(~ans) std::cout<<ans<<'\n';
else std::cout<<"orz\n";
return 0;
}
Kruskal
基于贪心的思想，使用并查集维护状态（一个集合一棵树），将所有边从小到大排序后遍历，如果两个点不在同一棵树上，则将该边纳入 MST，合并这条边连通的两个端点的集合。
Kruskal 更适合 稀疏图。
\(\text{Code - with Kruskal by Forward Star and Disjoint Set Union, } 230 ms \text{ without O2}\)
#include<bits/stdc++.h>
#define ll long long
#define ld long double
const int N=5005,M=2e5+5;
struct edge { int from,to,w; } E[M];
void add(int u,int v,int w,int ord) { E[ord].from=u,E[ord].to=v,E[ord].w=w; }
int n,m,fa[N];
void init() { for(int i=1;i<=n;++i) fa[i]=i; }
int get(int x) { return fa[x]==x?x:fa[x]=get(fa[x]); }
void merge(int x,int y) { fa[get(y)]=get(x); }
int kruskal() {
init();
std::sort(E+1,E+m+1,[](const edge &a,const edge &b){ return a.w<b.w; });
int ans=0,tot=0; edge *it=E;
while(++it<E+m+1) {
if(get(it->from)==get(it->to)) continue;
ans+=it->w,merge(it->from,it->to),tot++;
if(tot==n-1) break;
}
return tot==n-1?ans:-1;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
std::cin>>n>>m;
for(int i=1,u,v,w;i<=m;++i) { std::cin>>u>>v>>w; add(u,v,w,i); }
int ans=kruskal();
if(~ans) std::cout<<ans<<'\n';
else std::cout<<"orz\n";
return 0;
}
最大生成树
有什么好说的呢…算法相同，其实就只把排序/比较大小反过来罢了。
大概就是这样。
次小生成树
分为 非严格次小生成树 和 严格最小生成树。差别其实就是是否有边权和 严格大于 MST 边权和。
简单来说，在找到 MST 后枚举未在 \(E_{MST}\) 中的边 \(u \to v\)，然后断开 \(u\) 到 \(v\) 的路径上的最长边，将当前边加入边集，寻找最小的边权和即可。对于严格最小生成树，考虑到最长边边权可能与当前边权相同，还要同时记录 次大值。
严格最小生成树的伪代码如下：
\[\begin{array}{ll} 1 & \textbf{Input. } \text{The number of vertexs and edges of the undigraph } G, \\ & \text{the edges of the graph } e, \text{which element in } e \text{ is } (u,v,w) \\ & \text{denoting that there is an edge between } u \text{ and } v \text{ weighted } w . \\ 2 & \textbf{Output. } \text{The sum of the weights of the edges in the set of edges } E_{S}.\\ & \text{Or formally, } \sum_{e \in E_{S}} w_e.\\ 3 & \textbf{Method. }\\ 4 & \text{initialize the disjoint set union} \\ 5 & mstlen \gets 0,E_M \gets \varnothing \\ 6 & \text{sort } e \text{ into nondecreasing order by weight } w \\ 7 & \textbf{for } \text{each } (u,v,w) \text{ ordered } i \text{ in the sorted } e\\ 8 & \qquad \textbf{if } u \text{ and } v \text{ are not connected in the disjoint set union } \\ 9 & \qquad \qquad mstlen \gets mstlen + w\\ 10 & \qquad \qquad \text{merge } u \text{ and } v \text{ in the disjoint set union}\\ 11 & \qquad \qquad E_M \gets E_M \bigcup \{(u,v,w)\} \\ 12 & dfs(u \gets 1,fa \gets 0) \text{ to initialize the binary-lifting funtions} \\ 13 & ans \gets \infty \\ 14 & \textbf{for } \text{each } (u,v,w) \text{ which is not in } E_M \text{ and satisfies the limit } u \neq v \\ 15 & \qquad lca \gets \operatorname{LCA}(u,v),tmp_1 \gets - \infty, tmp_2 \gets - \infty \\ 16 & \qquad tmp_1 \gets \text{the maximum weight on the path from } lca \text{ to } u \\ 17 & \qquad \textbf{if } tmp_1 = w \\ 18 & \qquad \qquad tmp_1 \gets \text{the sub-maximum weight on the path from } lca \text{ to } u \\ 19 & \qquad tmp_2 \gets \text{the maximum weight on the path from } lca \text{ to } v \\ 20 & \qquad \textbf{if } tmp_2 = w \\ 21 & \qquad \qquad tmp_2 \gets \text{the sub-maximum weight on the path from } lca \text{ to } v \\ 22 & \qquad \textbf{if } tmp_1 = tmp_2 = - \infty \\ 23 & \qquad \qquad \textbf{continue} \\ 24 & \qquad ans \gets \min \left( ans, mstlen- \max(tmp_1,tmp_2)+w \right) \\ 25 & \textbf{return }ans \end{array} \]放一段优美的 \(code\)：
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define forE(u) for(int p=head[u],v=E[p].to;p;p=E[p].next,v=E[p].to)
const int N=1e5+5,M=3e5+5;
const ll inf=1e18+9;
int n,m;
// set of edges module
bool used[M];
struct pr { int from,to; ll w; } prE[M];
inline void add(int u,int v,ll w,int id) { prE[id].from=u,prE[id].to=v,prE[id].w=w; }
int cnt,head[N];
struct edge { int to,next; ll w; } E[N<<1];
inline void addedge(int u,int v,ll w) { E[++cnt].to=v,E[cnt].w=w,E[cnt].next=head[u],head[u]=cnt; }
// DSU module
int fa[N];
void init() { for(int i=1;i<=n;++i) fa[i]=i; }
int get(int x) { return fa[x]==x?x:fa[x]=get(fa[x]); }
void merge(int x,int y) { fa[get(y)]=get(x); }
// kruskal module
ll kruskal() {
init();
std::sort(prE+1,prE+m+1,[](const pr &a,const pr &b){ return a.w<b.w; });
int tot=0; ll ans=0; pr *it=prE;
while(tot<n-1) {
it++; if(it==prE+m+1) break;
if(get(it->from)==get(it->to)) continue;
ans+=it->w,used[it-prE]=1,merge(it->from,it->to),tot++;
addedge(it->from,it->to,it->w),addedge(it->to,it->from,it->w);
}
return ans;
}
// MST module
int dep[N],anc[22][N];
ll mx[22][N],sec[22][N];
void dfs(int u,int f) {
dep[u]=dep[f]+1,anc[0][u]=f,sec[0][u]=-inf;
for(int i=1;(1<<i)<=dep[u];++i) {
anc[i][u]=anc[i-1][anc[i-1][u]];
ll tmp[]={mx[i-1][u],mx[i-1][anc[i-1][u]],sec[i-1][u],sec[i-1][anc[i-1][u]]};
std::sort(tmp,tmp+4);
mx[i][u]=tmp[3];
int ptr=2;
while(~ptr && tmp[ptr]==tmp[3]) ptr--;
sec[i][u]=~ptr?tmp[ptr]:-inf;
}
forE(u) if(v!=f) mx[0][v]=E[p].w,dfs(v,u);
}
int LCA(int u,int v) {
if(dep[v]>dep[u]) std::swap(u,v);
int d=dep[u]-dep[v];
for(int i=20;~i;--i) if(d&(1<<i)) u=anc[i][u];
if(u==v) return u;
for(int i=20;~i;--i) if(anc[i][u]!=anc[i][v]) u=anc[i][u],v=anc[i][v];
return anc[0][u];
}
ll query(int u,int v,ll w) {
ll ans=-inf;
if(dep[v]>dep[u]) std::swap(u,v);
int d=dep[u]-dep[v];
for(int i=20;~i;--i) if(d&(1<<i)) {
if(mx[i][u]==w) ans=std::max(ans,sec[i][u]);
else ans=std::max(ans,mx[i][u]);
u=anc[i][u];
}
return ans;
}
// beautiful main program
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
std::cin>>n>>m;
for(int i=1,u,v,w;i<=m;++i) { std::cin>>u>>v>>w; add(u,v,w,i); }
ll mstlen=kruskal(),ans=inf; dfs(1,0);
for(int i=1;i<=m;++i) {
if(used[i] || prE[i].from==prE[i].to) continue;
int lca=LCA(prE[i].from,prE[i].to);
ll tmp1=query(prE[i].from,lca,prE[i].w),tmp2=query(prE[i].to,lca,prE[i].w);
if(tmp1==-inf && tmp2==-inf) continue;
ans=std::min(ans,mstlen-std::max(tmp1,tmp2)+prE[i].w);
}
std::cout<<ans<<'\n';
return 0;
}