最常用的化解技巧是建虚点。
DAY 1
跑最短路也是可以建虚点的。
Dijsktra
Dijsktra 中也需要记录 vis[] 表示当前点的最短路是否已经确定，否则可能造成重复枚举同一个点周围的边，导致冗余的松弛尝试，使时间变慢。
只要出现负权边，Dijsktra 即不能使用。
注意：对于二重费用（在第一重费用最小的同时使第二重费用最小）的问题，用 SPFA 极易 TLE。这时可以采用重新重载小于号的方法。在普通的 Dijsktra 中，堆顶存放的是 dis 最小的点，每次取出这个点对其周围的点进行松弛；而在二重费用的题目中，则可以把这个规则进行改进，即堆顶保存 dis 和 fee 都最小的点。这样可以保证每个点从堆中取出来的时候，都取到了二重费用的最小值。
struct node {
int u; ll dis, fee;
bool operator < (const node &rhs) const {
if (dis != rhs.dis)
return dis > rhs.dis;
return fee > rhs.fee;
// 二重费用的重载小于号
}
node(int src_u, ll src_dis, ll src_fee) {
u = src_u;
dis = src_dis;
fee = src_fee;
}
};
priority_queue<node> q;
void dijsktra() {
memset(dis, 0x3f, sizeof(dis));
memset(fee, 0x3f, sizeof(fee));
dis[s] = fee[s] = 0;
q.push(node(s, 0, 0));
while (!q.empty()) {
int u = q.top().u;
q.pop();
if (vis[u])
continue;
vis[u] = true;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to; ll w = edge[i].w, c = edge[i].c;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
fee[v] = fee[u] + c;
// 更新最小费用
q.push(node(v, dis[v], fee[v]));
} else if (dis[u] + w == dis[v] && fee[u] + c < fee[v]) {
fee[v] = fee[u] + c;
q.push(node(v, dis[v], fee[v]));
// 似乎这里不再入堆也是可以的
}
}
}
return ;
}SPFA
记得每次从队列取出点的时候，要把 vis[u] 清为 false，否则原地爆炸。
SPFA 判负环时，dfs - SPFA 固然是个又好又快的方法，然而我觉得通用性不如下面这种方法强：记录每个点当前最短路径上的点数 cnt[u]，若发现 cnt[u] > n 则说明出现负环。当然，这种做法的复杂度为$O(mn)$，很容易就被卡掉了；不过，大部分情况下，加上快读、inline、register 还是能够卡过。
bool SPFA() {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
while (!q.empty())
q.pop();
dis[1] = 0;
cnt[1] = 1;
// 节点数从 1 开始
q.push(1);
while (!q.empty()) {
int u = q.front();
vis[u] = false;
q.pop();
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to, w = edge[i].w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if (cnt[v] > n)
return true;
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
return false;
}差分约束
差分约束系统推出的条件，是跑完 SPFA 之后整张图所满足的。所以，等价条件 dis[u] + w <= dis[v] 该跑 最长路，dis[u] + w >= dis[v] 该跑 最短路。
最长路型差分约束系统的条件转换：
- $a-b\geq c \Leftrightarrow$
dis[b] + c <= dis[a]$\Leftrightarrow$build_edge(b, a, c) - $a-b\leq c \Leftrightarrow$
dis[a] - c <= dis[b]$\Leftrightarrow$build_edge(a, b, -c) - $a=b\Leftrightarrow$
build_edge(a, b, 0), build_edge(b, a, 0)
建完所有关系边之后，为了获取整张图是否存在负环的信息，一种方法是一个一个连通块地跑；另一种方法是新建虚点 0 并从虚点向所有点连一条长度为$0$的有向边，最后 SPFA(0) 即可。
最短路树
等长路径字典序最小 的最短路树的生成方式：维护一个 conn[] 表示当前点是否被连入最短路树。按编号从小到大枚举节点$u$，这样就能保证是按照字典序从小到大枚举；寻找$u$所指向的所有结点$v$，如果 conn[v] == false 并且这条边满足最短路树的性质，则证明当前这条边可以连入最短路树，那么直接在 edge2 上建边即可。
// https://www.luogu.org/problem/P5201
void build_tree() {
conn[1] = true;
for (int u = 1; u <= n; u++)
for (int i = head1[u]; i; i = edge1[i].next) {
int v = edge1[i].to, w = edge1[i].w;
if (conn[v])
continue;
if (dis[u] + w == dis[v]) {
conn[v] = true;
build_edge(edge2, head2, id2, u, v, 1);
build_edge(edge2, head2, id2, v, u, 1);
}
}
return ;
}DAY 2
缩点
缩完点建新图的时候，一定要记住 新图里点 $u$ 的编号是 scc[u]，千万不要逮着原图的点建图（多次死亡）。
缩点的时候要考虑到 两点环 的可能，所以不能判断$v$是否为父亲，而应该考虑$v$是否在栈内。
void tarjan(int u) {
dfn[u] = low[u] = ++cnt;
s[++top] = u, ins[u] = true;
for (register int i = h1[u]; i; i = e1[i].next) {
int v = e1[i].to;
if (!dfn[v]) {
tarjan(v);
low[u] = my_min(low[u], low[v]);
} else if (ins[v])
low[u] = my_min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
scc_cnt++;
int v;
do {
v = s[top--];
ins[v] = false;
scc[v] = scc_cnt;
p2[scc_cnt] += p[v];
} while (v != u);
}
}割点
割点需要特判 dfs 树的树根（也就是代码中的 fa ），具体为：若 fa 在 dfs 树中的儿子个数$\geq2$，则 fa 也是一个割点。
而对于一般的点$u$，只有在没有搜过$u$的情况下才会考察$u$是否为一个割点；不然就用 dfn[v] 更新 low[u] 即可。
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++dfscnt;
int cnt = 0;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (!dfn[v]) {
tarjan(v, fa);
// 注意是把 fa 下传
low[u] = min(low[u], low[v]);
if (u != fa && low[v] >= dfn[u])
cut[u] = true;
// 普通的点
if (u == fa)
cnt++;
// 特判 fa 的情况
} else
low[u] = min(low[u], dfn[v]);
// 这里不需要再带上判割点的语句
}
if (u == fa && cnt > 1)
cut[u] = true;
return ;
}桥
在基环树上，断掉所有的桥，剩下的边就是环上的边。
tarjan 找桥的过程中，需要判断反向边。
void tarjan(int u, int pre) {
dfn[u] = low[u] = ++dfscnt;
for (int i = head[u]; i; i = edge[i].next) {
if (i == (pre ^ 1))
continue;
int v = edge[i].to;
if (!dfn[v]) {
tarjan(v, i);
if (low[v] > dfn[u])
cut[i] = true;
low[u] = min(low[u], low[v]);
} else
low[u] = min(low[u], dfn[v]);
}
return ;
}DAY 3
欧拉回路
半欧拉回路的起点必须为奇数度数点，而欧拉图的起点可以任意取。注意：有可能需要倒序记录路径。
void hierholzer(int u) {
for (int v = 'A'; v <= 'z'; v++)
if (G[u][v]) {
G[u][v] = G[v][u] = 0;
hierholzer(v);
}
res[tail--] = u;
return ;
}最小生成树
Kruskal
Kruskal 的复杂度由边数$m$决定，因此太稠密的图不能跑 Kruskal（然而这种情况并不多见）。
Prim
Prim 的思路类似 Dijsktra，并且主函数也只有一小点区别。也就是说，维护一个 dis[u] 表示点$u$到当前生成树的最短距离；每次找出不在生成树中的 dis[] 最小的点，并连入生成树中。当然，由于思路和 Dijsktra 相似，Prim 也是可以加堆优化的。不加堆优化的 Prim 在超级稠密图中的性能优于 Kruskal。
// Prim 的邻接矩阵写法
void prim() {
memset(dis, 0x3f, sizeof(dis));
for (int i = 1; i <= n; i++)
dis[i] = min(dis[i], G[1][i]);
int u = 1;
while (++tot < n) {
vis[u] = true;
int minn = 0x3f3f3f3f;
for (int i = 1; i <= n; i++)
if (!vis[i] && dis[i] < minn) {
u = i;
minn = dis[i];
}
ans += minn;
for (int i = 1; i <= n; i++)
if (!vis[i] && G[u][i] < dis[i])
dis[i] = G[u][i];
}
return ;
}最小生成森林
最小生成森林可以看作所有树的根都连到超级根上的最小生成树，所以从超级根向每一个可以作为树根的点连一条边，即可获得最小生成森林。这里又用到了 建虚点 的方法。当然，最小生成森林也可以简单地用并查集维护，只需要统计 fa[i] == i 的点即可。
事实上，只要涉及到 一条边减少一个联通块 的问题，极有可能与最小生成树 / 最小生成森林相关。
DAY 4
二分图染色
只要一个图中没有奇环，那么这个图就是一个二分图。通常可以使用黑白染色法把一个图转化为二分图。二分图的核心在于 如何建图。
二分图的题目中，点和边的实际意义是很灵活的，比如可以把坐标系上的点$P$当成边，从$x_P$向$y_P$连一条边；也可以把一个网格图黑白染色后两两连边，每条边代表将这条边所连的两个点放在同一个矩形里。
不过，因为二分图中的点只有 x[] 和 y[] 两列，所以对于二维网格图上的点，需要先把点映射到一个数字上，然后才能放到点列当中。
二分图匹配
匈牙利算法 的本质是寻找增广路（也就是进行匹配协商）。复杂度为$O(nm)$。由于 vis[u] 记录的是点$u$是否在当前增广路上，所以 每次找增广路后都需要把 vis[] 清零。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;
int cx[MAXN], cy[MAXN], G[MAXN][MAXN];
bool vis[MAXN];
int n, m, e, ans = 0;
bool hungary(int x) {
for (int y = 1; y <= m; y++)
if (!vis[y] && G[x][y]) {
vis[y] = true;
// 标记当前点已经在增广路上
if (!cy[y] || hungary(cy[y])) {
// 若还能找到增广路 / 进行协商
cx[x] = y;
cy[y] = x;
return true;
}
}
return false;
}
int main() {
memset(cx, 0, sizeof(cx));
memset(cy, 0, sizeof(cy));
// 必须初始化
scanf("%d %d %d", &n, &m, &e);
for (int u, v; e; e--) {
scanf("%d %d", &u, &v);
if (u > n || v > m)
continue;
G[u][v] = 1;
}
for (int i = 1; i <= n; i++) {
memset(vis, 0, sizeof(vis));
// 每次都必须 memset()
ans += hungary(i);
}
// 从每个点尝试寻找增广路，若找到增广路则 ans++
printf("%d", ans);
return 0;
}当然，每次对 vis[] 进行一次 memset() 比较慢。为了加速，可以把 vis[] 改成时间戳，也就是下面的写法：
bool hungary(int x) {
for (int y = 1; y <= n; y++)
if (G[x][y] && vis[y] != cur) {
vis[y] = cur;
if (!cy[y] || hungary(cy[y])) {
cx[x] = y;
cy[y] = x;
return true;
}
}
return false;
}
int match() {
memset(cx, 0, sizeof(cx));
memset(cy, 0, sizeof(cy));
memset(vis, 0, sizeof(vis));
cur = 1;
int res = 0;
for (int i = 1; i <= n; i++, cur++)
res += hungary(i);
return res;
}二分图的一些性质
最小点覆盖
最小点覆盖： 选取最少的一些点使得所有边都与这些点相连。
二分图中，最小点覆盖$=$最大匹配。
例题： 有一些障碍物位于一张$n\times n$的网格图上，每次可以消除一行或者一列上的所有障碍物，求最少需要消除多少次才能清除所有障碍物。
分析： 对于每个障碍物$(x,y)$，从$x$向$y$连一条边，每条边代表一个障碍物。那么可以看出，只要选出一个点$x$，与$x$相连的所有边（即横坐标为$x$的所有障碍物）都会被覆盖；而题目要求所有边都被覆盖。所以，问题就转化为了最小点覆盖。
// http://poj.org/problem?id=3041
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
const int MAXN = 510;
int n, k;
int G[MAXN][MAXN], cx[MAXN], cy[MAXN];
bool vis[MAXN];
bool hungary(int x) {
for (int y = 1; y <= n; y++)
if (G[x][y] && !vis[y]) {
vis[y] = true;
if (!cy[y] || hungary(cy[y])) {
cx[x] = y;
cy[y] = x;
return true;
}
}
return false;
}
int match() {
int res = 0;
for (int i = 1; i <= n; i++) {
memset(vis, 0, sizeof(vis));
res += hungary(i);
}
return res;
}
int main() {
memset(cx, 0, sizeof(cx));
memset(cy, 0, sizeof(cy));
scanf("%d %d", &n, &k);
for (int x, y; k; k--) {
scanf("%d %d", &x, &y);
G[x][y] = 1;
}
printf("%d", match());
return 0;
} 最小边覆盖
最小边覆盖： 选取最少的一些边使得所有点都与这些边相连。
二分图中，最小边覆盖$=$总点数$-$最大匹配数。
例题： 有一个网格，上面有一些可选点，每次可以覆盖一个$1\times2$大小的矩形，求出把所有点都覆盖住的最小覆盖次数。
分析： 考虑如何建图。先把图黑白染色，对于每个黑色可选点，向上下左右的白色可选点连边。对于任意一条边，选取这条边代表这条边所连的两点在同一矩形内；而题目要求所有点都被覆盖。所以，问题就转化为了最小边覆盖。
// poj.org/problem?id=3020
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
const int MAXN = 3e3 + 10;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int G[MAXN][MAXN];
int T, h, w, n;
char s[MAXN][MAXN];
int cx[MAXN], cy[MAXN];
bool vis[MAXN];
bool accept(int x, int y) {
return x > 0 && x <= h && y > 0 && y <= w;
}
int getid(int x, int y) {
return (x - 1) * w + y;
}
// 需要把点映射到一个数上，方便连边
bool hungary(int x) {
for (int y = 1; y <= n; y++)
if (!vis[y] && G[x][y]) {
vis[y] = true;
if (!cy[y] || hungary(cy[y])) {
cx[x] = y;
cy[y] = x;
return true;
}
}
return false;
}
int match() {
int res = 0;
for (int i = 1; i <= n; i++) {
memset(vis, 0, sizeof(vis));
res += hungary(i);
}
return res;
}
int init() {
memset(G, 0, sizeof(G));
memset(cx, 0, sizeof(cx));
memset(cy, 0, sizeof(cy));
int res = 0;
for (int x = 1; x <= h; x++)
for (int y = 1; y <= w; y++)
if (s[x][y] == '*') {
res++;
if ((x + y) & 1)
continue;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (!accept(nx, ny))
continue;
if (s[nx][ny] == '*')
G[getid(x, y)][getid(nx, ny)] = 1;
}
}
return res;
}
int main() {
scanf("%d", &T);
while (T-- && scanf("%d %d", &h, &w)) {
for (int i = 1; i <= h; i++)
scanf("%s", s[i] + 1);
n = h * w;
int tot = init();
printf("%d\n", tot - match());
}
return 0;
}DAY 5
树链剖分
剖完以后$u,v$的跳转非常易错，需要判断的是 top[u] 和 top[v] 的深度关系 而不是 u 和 v。
void Update(int u, int v, ll c) {
c %= p;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]])
swap(u, v);
// 注意是 dep[top[u]] < dep[top[v]]
edit_tree(1, dfn[top[u]], dfn[u], c);
u = fa[top[u]];
}
if (dep[u] > dep[v])
swap(u, v);
edit_tree(1, dfn[u], dfn[v], c);
return ;
}DAY 6
树上问题
一般树上问题的解决思路是考虑子树，然后考虑子树能够上传些什么给父节点。比如树上链问题，单独考虑一棵子树的话，子树内的链可以分为三种情况：
- 链在子树内，且不经过根节点；
- 链在子树内，且经过根节点；
- 链不全在子树内。
分别考虑每种情况对应的处理方法，就可以分治地解决一些树上问题（2018 D1T3）。
树的重心
定义：选取树上的一个点作为树根，使得最大子树最小，则这个点为树的重心。
求法：以任意点为根跑一遍 dfs，然后统计 max(size[v], n - size[u] - 1) 最小的点，即可获得重心。
一些性质
树中所有点到某节点的距离和中，到重心的距离和是最小的；若有两个重心，则其距离和相等；
把两个树通过一条边相连得到一棵新树，那么新树的重心在连接原来两个树的重心的路径上；
添加或删除一个叶子，那么树的重心最多只移动一个点。
树的直径
定义：树上任意两点的最长距离为树的直径。
直径共有两种求法，都是$O(n)$。
贪心求法：正反两遍 dfs，第一次以任意节点为根 dfs 到最远的点$u$，第二次从$u$开始 dfs 到最远的点$v$，则$u\rightarrow v$即树的直径。
int dia = 0, p;
void dfs(int u, int fa, int pre) {
if (pre > dia) {
dia = pre;
p = u;
}
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to, w = edge[i].w;
if (v == fa)
continue;
dfs(v, u, pre + w);
}
return ;
}
inline void prework() {
dfs2(1, 1, 0);
dfs2(p, p, 0);
return ;
}动规求法（适用于所有情况）：$f[u]$表示从$u$开始向下能够延伸的最长链长度，每次对于一个儿子$v$，先用$f[u]+f[v]+dis[u\rightarrow v]$更新答案，然后用$f[v]+dis[u\rightarrow v]$更新$f[u]$。这样可以保证不会重复计算同一条链。
一些性质
设两棵树的直径分别是$(u_1\rightarrow v_1), (u_2\rightarrow v_2)$，则用一条边将两棵树相连，新的直径$(u\rightarrow v)$一定满足$u,v\in \{u_1,u_2,v_1,v_2\}$；
若给树加一个节点，新的直径最多改变一个端点。
总结
再次强调图论的经典处理方法：建反图，建虚点，边排序。
在这些知识点中，有关树的部分很可能是和树形 dp 结合考察，因此要向两个方向试探，不能局限思维。点和边的意义也不能局限于常见的套路，比如二分图中，边的意义甚至是点。涉及到树上查询的问题，一般是用树上倍增实现；如果用树链剖分 + 线段树则时间复杂度会多出一个$logn$，这种情况下就需要用 ST 表使得单次查询复杂度达到$O(1)$。
总而言之，图论的难点就在于建模。
$\footnotesize\text{Weathering With You}$
重拾那份爱的勇气，纵使世界就这样疯狂下去，我毫不在意
跨越无尽黑夜，逃离阳光无法企及之地
无论是晴是雨，不管多远距离，也一定要去见你
当大地失去了重力，千年一遇的奇迹
我和你，十指相扣，翱翔天际
「呐，现在开始就要放晴了哦。」
——希望百分百晴天女孩的祈祷，也能驱散你心中的阴云。
$\large\texttt{by NCC-79601}$
$\footnotesize\text{Weathering With You}$