图论
最短路
Bellman-Ford：松弛 \(n-1\) 次，若第 \(n\) 次仍然有更新，那么有负环，\(O(nm)\)。
Dijskra：每一次取出最短路最小的点进行松弛，用堆加速比较过程，记得一个点只会被松弛一遍，\(O(m\log m)\)。
SPFA：使用队列优化 Bellman-Ford 即可，具体地，每次松弛一个节点的时候，找到所有接下来可能被松弛的点，塞入队列，判负环的方式是，记录最短路长度，大于 \(n-1\) 就说明有负环，复杂度同样是 \(O(nm)\)。
Johnson：带负权全源最短路，为所有的点附上势能 \(h_u\)，将边权改为 \(w(u,v)+h_u-h_v\)，期望其为正，对于每一次最短路的询问，跑 Dijskra 算法。\(h_u\) 的设计可以先跑若干遍 Bellman-Ford，记得把最短路多算的势能减掉。
Floyd 与传递闭包：枚举 \(k\)，枚举 \(i\)，枚举 \(j\)，转移 \(f_{i,k}+f_{k,j}\to f_{i,j}\) 即可，传递闭包可以 bitset 除个 \(\omega\)。
贴一个 Johnson 的实现：
const int N=3e3+5;
const ll inf=1e9;
vector<pii> G[N];
int n,h[N];
bool vis[N];
void dijskra(int s,ll *dis) {
FOR(i,1,n) vis[i]=0,dis[i]=inf;
dis[s]=0;
priority_queue<pii> pq; pq.push(0,s);
while(sz(pq)) {
int u=pq.top().se; pq.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto [v,w]:G[u]) if(dis[u]+w<dis[v])
dis[v]=dis[u]+w,pq.push(-dis[v],v);
}
}
ll dis[N];
int main() {
n=read(); int m=read();
FOR(i,1,m) {
int x=read(),y=read(),w=read();
G[x].pb(y,w);
}
FOR(i,1,n) {
bool fl=0;
FOR(u,1,n) for(auto [v,w]:G[u])
if(h[u]+w<h[v]) h[v]=h[u]+w,fl=1;
if(fl&&i==n) return puts("-1"),0;
if(!fl) break;
}
FOR(u,1,n) for(auto &[v,w]:G[u]) w+=h[u]-h[v];
FOR(i,1,n) {
ll ans=0; dijskra(i,dis);
FOR(j,1,n) if(dis[j]!=inf) dis[j]=dis[j]+h[j]-h[i];
FOR(j,1,n) ans+=j*dis[j];
printf("%lld\n",ans);
}
}
差分约束
形如 \(x_a-x_b\le c\) 的不等式组，求其一组解，被称为差分约束系统。
所有约束可以被写为 \(x_i+c\ge x_j\) 的形式，所以可以将 \(i\to j\) 长度设为 \(c\)，然后跑最短路。
一般需要使用 SPFA 或者 Bellman-Ford，出现负环就无解。
同余最短路
取任意物品体积作为基准值，跑模 \(m\) 意义下的完全背包，绕着这个环转两圈，即可实现转移。
这可比最短路好写多了！
最小生成树
Kruskal：按边权排序，然后维护连通性，\(O(m\log m)\)。
Boruvka：维护所有连通块，每次找出每一个连通块到连通块外部最小的边，将这些边加入最小生成树，递归下去做，\(O(m\log n)\)，优势在特殊边权完全图。
无向图连通性
割点/割边：删去点/边后会增加连通块个数。
定义 \(dfn_u\) 表示 \(u\) 在 \(dfs\) 树上访问的顺序，\(low_u\) 表示 \(u\) 经过某一条边之后得到的 \(dfn\) 最小值，分三种情况讨论：
- \(dfn_u\to low_u\)。
- \(u\to v\)，\(v\) 在 \(dfs\) 树上属于祖先，\(dfn_v\to low_u\)。
- \(u\to v\)，\(v\) 是 \(u\) 的儿子，\(low_v\to low_u\)。
判断割点条件：如果点 \(u\) 不是根，那么若对于某一条 \(dfs\) 树上的边，存在 \(low_v\ge dfn_u\)，那么 \(v\) 只能到 \(u\)，删了 \(u\) 之后不连通。
如果点 \(u\) 是根，因为无向图 \(dfs\) 树上只有返祖边，所以有两个儿子就一定是割点。
判断割边条件：对于某一条边 \(u\to v\)，那么若 \(low_v>dfn_u\)，则这条边是割边。
边双联通分量：无论删去哪一条边，图依然联通的连通块，被称为边双联通分量，显然，将割边全部去掉即可求出所有边双。
点双联通分量：维护栈，若 \(u\to v\)，\(dfn_u=low_v\)，则当前栈中 \(u\) 上的节点构成一个点双，\(u\) 不退栈但是形成点双。
圆方树
对原图进行点双的一个缩点，对每一个点双新建一个点，这个点向所有点双内的点连边，称其为方点，而原图中的点称为圆点。
圆方树的优势是可以将图转化为树，在树上进行维护。
有向图连通性
强连通分量：任意两点互相可达的图。
同样定义 \(dfn\) 和 \(low\)，对于树边 \(low_v\to low_u\)，同时维护栈，若 \(v\) 在栈中 \(dfn_v\to low_u\)。
若 \(dfn_u=low_u\)，那么 \(u\) 及 \(u\) 往上形成强连通分量，弹栈。
2-SAT
对每个命题开两个点 \(p\) 和 \(\lnot p\)，考虑如下条件的连边：
- \(p\to q\)：连边 \((p,q)\) 和 \((\lnot q,\lnot p)\)。
- \(p\lor q\)：连边 \((\lnot p,q)\) 和 \((q,\lnot p)\)
- \(p\) 一定成立：连边 \((\lnot p,p)\)。
那么，处在同一个强连通分量的命题一定同时成立或不成立，所以缩点后即可判断是否有解。
一组可行解的构造是简单的：根据 SCC 的编号的大小关系，若 \(id_x<id_{\lnot x}\)，那么取 \(x\)，否则取 \(\lnot x\)。
网络流
在 \(G=(V,E)\) 上，定义 \(f(u,v)\) 表示 \((u,v)\) 的流量，\(c(u,v)\) 表示 \((u,v)\) 的流量上限，那么 \(f\) 有如下性质：
- \(f(u,v)\le c(u,v)\)；
- \(f(u,v)=-f(v,u)\)；
- \(\forall i\not= S,T\)，\(\sum f(u,i)=\sum f(i,v)\)。
网络流有如下定义：
- \(\sum f(S,i)=\sum f(i,T)\)，这个和称为当前流 \(f\) 的流量。
- 定义 \(f\) 在 \(G\) 上的残量网络 \(G_f=(V,E_f)\) 为容量函数为 \(c_f=c-f\) 的网络，可以认为残量网络就是去掉满流的边，容量减去流量的网络。
- 定义增广路为 \(G_f\) 上 \(S\) 到 \(T\) 的一条路径。
- 将 \(V\) 分成不交的两个集合 \(A,B\)，其中 \(S\in A\)，\(T\in B\)，称这种划分方式为割，割的容量为割边的容量和，流量为割边的流量和。
Dinic 算法被用来求出一个网络的最大流，算法流程如下：
首先，在残量网络上 BFS，将网络分层。
接下来，使用 DFS 进行多路增广，每次跳过已经被增广满的边。
最大流最小割定理：最大流等于最小割。