图论。
强连通图 与 弱连通图 。
最短路 。dij 不支持负权。显然 值得一提的是利用斐波那契堆m+nlogn 。
一张 边权都是2的整数次幂 考虑 一下直接 结构体维护这个2的整次幂数组但比大小 太慢 考虑利用数据结构维护。
主席树维护每一位 （当然压位也是可以的 但却不必要 hash值维护 每个区间的值然后就可以快速判断辣。
我们还需要维护一个+1的操作 这就涉及到简单 的线段树上二分。和区间整体赋值问题。
floyd 设x y z 表示 x y 不经过z 这个点的最短路 。经典题目 应该是 分治一下 但是我不太回写，回来写一遍。
spfa 值得一提的是 复杂度 为nm 这个很容易被卡掉 具体卡掉代码如下。
#include <bits/stdc++.h> using namespace std; int N = 5000, M = 4*N-1, L = N; int main() { freopen("in", "w", stdout); printf("%d %d %d ", N*2+1, M, L); for(int i=1; i<N; i++) printf("%d %d %d ", i, i+1, 1); printf("%d %d %d ", N, N*2+1, 1); for(int i=1; i<=N; i++) printf("%d %d %d ", i, i+N, N-i+1); for(int i=1; i<=N; i++) printf("%d %d %d ", i+N, i, 1); for(int i=1; i<N; i++) printf("%d %d %d ", i+N, i+N+1, 1); for(int i=1; i<=L; i++) printf("%d ", i); putchar(' '); return 0; }
当然还能在负环上面判断 当然dfs套spfa 这个方法有的时候更快一点。当然floyd 也是可以的。
边权递增最短路。
排序边权 然后 一条一条加入 然后每次松弛一下即可。
某个最短路的题目：
有m条边 连接两个节点 有k条铁路 连接1到某个点 求最多去掉多少条道路使得 1到任意节点的最短路不变。
这道题
n个点m条边 dij 表示两点之间最短路 每个点都有点权 求 min{2*dij + aj};
这将等价于 min{dij+d 0 j} 即可。
n 个点 m 条边 其中有k 个关键点求 k个关键点之间两两之间最短路的最小值。
咕了。
一张图 A B C 的基地 随意选 然后 求一个点 到A B C 的最短路和最小 求 期望和。
不会 咕了。膜改 bfs 一下 即可。