CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
这里用类似邻接表的方法存图。有的算法可能需要邻接矩阵，详见线性代数部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct Graph
{
struct Vertex
{
vector<int> o, i; //相关出边和入边编号
int siz, dep, top, dfn; //树链剖分中使用，依次代表子树节点数、深度、所在链的顶端节点、dfs序
};
struct Edge : pair<int, int>
{
ll len, cap; //边长、容量，图论算法使用
};
vector<Vertex> v; //点集
vector<Edge> e; //边集
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
if (ed.first == ed.second)
return; //如果有需要请拆点
v[ed.first].o.push_back(e.size());
v[ed.second].i.push_back(e.size());
e.push_back(ed);
}
int ch(int u, int i = 0) { return e[v[u].o[i]].second; } //u的第i个孩子节点
int fa(int u, int i = 0) { return e[v[u].i[i]].first; } //u的第i个父节点
};
最短路
Dijkstra 算法
使用示例，适用于边权为正的情况（无论有向图还是无向图），用于求单源最短路。
直接给出其优先队列优化的版本。另外，由于priority_queue并不提供修改优先级的操作，为避免重复扩展，这里选择将新元素直接插入队列并在运行时判断该点是否被处理，并不影响结果的正确性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct Dijkstra : Graph
{
vector<ll> d;
vector<int> p;
Dijkstra(int n) : Graph(n) {}
void ask(int s)
{
d.assign(v.size(), INF);
p.assign(v.size(), e.size());
priority_queue<pair<ll, int>> q;
for (q.push(make_pair(d[s] = 0, s)); !q.empty();)
{
ll dis = -q.top().first;
int u = q.top().second;
if (q.pop(), d[u] < dis)
continue;
for (int i = 0, k, to; i != v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second,
d[to] > d[u] + e[k].len)
{
d[to] = d[u] + e[k].len, p[to] = k;
q.push(make_pair(-d[to], to));
}
}
}
};
BellmanFord 算法
使用示例，直接给出其队列优化、国内称之为 SPFA 算法的版本。较之 Dijkstra 算法，此算法不够快速稳定但是可以允许负边存在，当 s 到达负权回路时会直接返回 0。稀疏图上性能优秀。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct BellmanFord : Graph
{
vector<ll> d;
vector<int> p;
BellmanFord(int n) : Graph(n) {}
bool ask(int s)
{
d.assign(v.size(), INF);
p.assign(v.size(), e.size());
vector<int> cnt(v.size(), 0), flag(v.size(), d[s] = 0);
for (deque<int> q(cnt[s] = flag[s] = 1, s); !q.empty(); q.pop_front())
for (int u = q.front(), i = flag[u] = 0, k, to; i < v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second,
d[to] > d[u] + e[k].len)
{
d[to] = d[u] + e[k].len, p[to] = k;
if (!flag[to])
{
if (v.size() == ++cnt[to])
return 0;
flag[to] = 1, q.push_back(to);
}
}
return 1;
}
};
差分约束系统
按如下方式建图、跑 SPFA：
对每个不等式$x_i−x_j\leq d$，从$j$向$i$连一条边，边长为$d$。
若不等号的方向相反，即$x_i−x_j\geq d$，则在不等式两边同时乘以$-1$，变成$x_j−x_i\leq -d$，即从$i$到$j$连一条边，边长为$d$。
Floyed 求多源最短路
不连通的权置 INF。
1
2
3
4
5
6
7
8
void floyed(Mat &a, int n) // 其实一般手打即可，没必要套这个鬼模板…
{
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (a[i][j] > a[i][k] + a[k][j])
a[i][j] = a[i][k] + a[k][j];
}
Astar 求 k 短路
使用示例，在这个比较坑的例子中需要在调用前补一句if(s==t)++k;。k 下标从 0 开始，即最短路==第 0 短路。
朴素的想法是使用priority_queue从原点出发向外探索，当取出终点 t 第 k 次时就得到第 k 短路，类似 bfs 的思想，缺陷是越往后状态数越多。
我们在反向图上从$t\to s$跑 Astar 算法，通过优先展开到 s 近的状态，使搜索方向靠近答案，而不是一层一层全都展开，估价函数$f\approx g+h$，f 是估计的 s 到 t 的距离，g 是到达当前点已经点的花费，h 是预计剩下的花费。这里 h 取当前点的距离到 s 距离，可通过从 s 跑一遍 Dijkstra 可以预处理得出。
Astar 算法是只有到达终点的时候才能统计答案，这导致可能拓展很多个状态才能得到一个用来更新答案的有效状态。例如一个 n 元环，当我们到达终点之后,可能还要拓展 n 次才能得到下一个状态，于是时间复杂度就被卡到$O(nk)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct Astar : Dijkstra
{
vector<ll> ans;
Astar(int n) : Dijkstra(n) {}
void ask(int s, int t, int k)
{
Dijkstra::ask(s);
ans.assign(k, INF);
if (d[t] == INF)
return;
vector<int> cnt(v.size(), 0);
priority_queue<pair<ll, int>> q;
for (q.push(make_pair(-d[t], t)); cnt[s] < k && !q.empty();)
{
ll dis = -q.top().first;
int u = q.top().second;
if (u == s)
ans[cnt[s]] = dis;
if (q.pop(), ++cnt[u] > k)
continue;
for (int i = 0, k; i < v[u].i.size(); ++i)
k = v[u].i[i], q.push(make_pair(d[u] - d[e[k].first] - e[k].len - dis, e[k].first));
}
}
};
网络流
ISAP 求最大流
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct ISAP : Graph
{
ll flow;
vector<ll> f;
vector<int> h, cur, gap;
ISAP(int n) : Graph(n) {}
void add(Edge ed)
{
Graph::add(ed);
swap(ed.first, ed.second), ed.cap = 0;
Graph::add(ed);
}
ll dfs(int s, int u, int t, ll r)
{
if (r == 0 || u == t)
return r;
ll _f, _r = 0;
for (int &i = cur[u], k; i < v[u].o.size(); ++i)
if (k = v[u].o[i], h[u] == h[e[k].second] + 1)
{
_f = dfs(s, e[k].second, t, min(r - _r, e[k].cap - f[k]));
f[k] += _f, f[k ^ 1] -= _f, _r += _f;
if (_r == r || h[s] >= v.size())
return _r;
}
if (!--gap[h[u]])
h[s] = v.size();
return ++gap[++h[u]], cur[u] = 0, _r;
}
void ask(int s, int t)
{
h.assign(v.size(), 0);
cur.assign(v.size(), 0);
gap.assign(v.size() + 2, 0);
/*
for (deque<int> q(h[t] = gap[t] = 1, t); !q.empty(); q.pop_front()) //优化，加了能快一点
for (int i = 0, u = q.front(), k, to; i < v[u].o.size(); ++i)
if (to = e[v[u].o[i]].second, !h[to])
++gap[h[to] = h[u] + 1], q.push_back(to);
*/
for (f.assign(e.size(), flow = 0); h[s] < v.size();)
flow += dfs(s, s, t, INF);
}
};
PrimalDual 求费用流
使用示例，定义一条边的费用为流量*边长，求总费用最小的最大流。性能优秀，只能跑非负权图。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct PrimalDual : Graph
{
ll flow, cost;
vector<ll> f;
PrimalDual(int n) : Graph(n) {}
void add(Edge ed)
{
Graph::add(ed);
swap(ed.first, ed.second), ed.cap = 0, ed.len *= -1;
Graph::add(ed);
}
void ask(int s, int t) //询问s到t的最小费用最大流，答案存在flow、cost中
{
vector<int> p(v.size(), e.size());
vector<ll> d(v.size(), INF), h(v.size(), 0);
for (f.assign(e.size(), flow = cost = 0);;)
{
priority_queue<pair<ll, int>> q;
for (q.push(make_pair(d[s] = 0, s)); !q.empty();)
{
ll dis = -q.top().first;
int u = q.top().second;
if (q.pop(), d[u] < dis)
continue;
for (int i = 0, k, to; i < v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second,
e[k].cap > f[k] && d[to] > d[u] + e[k].len + h[u] - h[to])
{
d[to] = d[u] + e[k].len + h[u] - h[to], p[to] = k;
q.push(make_pair(-d[to], to));
}
}
if (d[t] == INF)
return;
for (int i = 0; i < d.size(); ++i)
if (d[i] != INF)
h[i] += d[i], d[i] = INF;
ll _f = INF;
for (int u = t; u != s; u = e[p[u]].first)
_f = min(_f, e[p[u]].cap - f[p[u]]);
for (int u = t; u != s; u = e[p[u]].first)
cost += _f * e[p[u]].len, f[p[u]] += _f, f[p[u] ^ 1] -= _f;
flow += _f;
}
}
};
EK 求费用流
使用示例，定义一条边的费用为流量*边长，求总费用最小的最大流。BellmanFord 算法找增广路，可能被卡但是可以跑负费用流（最大费用流）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct EdmondKarp : Graph
{
ll flow, cost;
vector<ll> f;
EdmondKarp(int n) : Graph(n) {}
void add(Edge ed)
{
Graph::add(ed);
swap(ed.first, ed.second), ed.cap = 0, ed.len *= -1;
Graph::add(ed);
}
void ask(int s, int t)
{
vector<int> p(v.size(), e.size());
for (f.assign(e.size(), flow = cost = 0);;)
{
vector<ll> d(v.size(), INF);
vector<int> flag(v.size(), d[s] = 0);
for (deque<int> q(flag[s] = 1, s); !q.empty(); q.pop_front())
for (int u = q.front(), i = flag[u] = 0, k, to; i < v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second,
e[k].cap > f[k] && d[to] > d[u] + e[k].len)
{
d[to] = d[u] + e[k].len, p[to] = k;
if (!flag[to])
q.push_back(to), flag[to] = 1;
}
if (d[t] == INF)
return;
ll _f = INF;
for (int u = t; u != s; u = e[p[u]].first)
_f = min(_f, e[p[u]].cap - f[p[u]]);
for (int u = t; u != s; u = e[p[u]].first)
cost += _f * e[p[u]].len, f[p[u]] += _f, f[p[u] ^ 1] -= _f;
flow += _f;
}
}
};
ZKW 求费用流
使用示例，定义一条边的费用为流量*边长，求总费用最小的最大流。
对于最终流量较大，而费用取值范围不大的图，或者是增广路径比较短的图（如二分图），zkw 算法都会比较快，原因是充分发挥优势。比如流多说明可以同一费用反复增广，费用窄说明不用改太多距离标号就会有新增广路，增广路径短可以显著改善最坏情况，因为即使每次就只增加一条边也可以很快凑成最短路。如果恰恰相反，流量不大，费用不小，增广路还较长，就不适合 zkw 算法了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct ZKW : Graph
{
ll flow, cost;
vector<ll> h, f;
vector<int> vis;
ZKW(int n) : Graph(n) {}
void add(Edge ed)
{
Graph::add(ed);
swap(ed.first, ed.second), ed.cap = 0, ed.len *= -1;
Graph::add(ed);
}
ll dfs(int u, int t, ll r)
{
if (r == 0 || u == t)
return r;
if (vis[u])
return 0;
ll _f = vis[u] = 1, _r = 0;
for (int i = 0, k; r > _r && i < v[u].o.size(); ++i)
if (k = v[u].o[i], h[e[k].second] + e[k].len == h[u])
_f = dfs(e[k].second, t, min(r - _r, e[k].cap - f[k])), f[k] += _f, f[k ^ 1] -= _f, _r += _f;
return _r;
}
void ask(int s, int t)
{
h.assign(v.size(), 0);
vis.assign(v.size(), 0);
for (f.assign(e.size(), flow = cost = 0);;)
{
ll _f = dfs(s, t, INF), d = INF;
flow += _f, cost += _f * h[s];
for (int u = 0; u < v.size(); ++u)
for (int i = 0, k; vis[u] && i < v[u].o.size(); ++i)
if (k = v[u].o[i], !vis[e[k].second] && e[k].cap > f[k])
d = min(d, e[k].len + h[e[k].second] - h[e[k].first]);
if (d == INF)
return;
for (int i = 0; i < v.size(); ++i)
if (vis[i])
h[i] += d, vis[i] = 0;
}
}
};
上下界有源汇网络流
T 向 S 连容量正无穷的边，将有源汇转化为无源汇。每条边容量减去下界，设$in[i]$表示流入 i 的下界之和减去流出 i 的下界之和。新建超级源汇 SS,TT，对于$in[i]>0$的点，SS 向 i 连容量为$in[i]$的边。对于$in[i]<0$的点，i 向 TT 连容量为$−in[i]$的边。
求出以 SS,TT 为源汇的最大流，如果等于$\sum ini$则存在可行流。再求出以 S,T 为源汇的最大流即为最大流。
费用流：建完图后等价于求以 SS,TT 为源汇的的费用流。
上下界费用流：先把下界的费用加入答案。
判断边是否属于某一割集
在残余网络 (还有流量的边) 中求强连通分量，顶点不在同一 SCC 且满流的边。
判断边是否为全部最小割集的边： 在上一条的基础上，还要满足起点与 S 在同一 SCC，且终点与 T 在同一 SCC。
线性规划转费用流
首先添加松弛变量，将不等号都变为等号。分别用下一个式子减去上一个式子，如果每个变量只出现了两次且符号一正一负，那么可以转化为费用流。对于每个式子建立一个点，那么每个变量对应一条边，从一个点流出，向另一个点流入。这样，对于等式右边的常数，如果是正的，对应从源点向该点连一条流量 C，费用 0 的边；如果是负的对应从该点向汇点连一条流量 −C，费用 0 的边。对于每个变量，从它系数为正的式子向系数为负的式子连一条容量为 inf，费用为它在目标函数里系数的边。这样网络流模型就构造完毕了。
欧拉路
使用示例，给定无孤立结点图 G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路。
- 无向图：当仅当该图所有顶点的度数为偶数（此时为回路），或除两个度数为奇数外（作为路径的起点和终点）、其余全为偶数。
- 有向图：当仅当该图所有顶点出度=入度（此时为回路），或一个顶点出度=入度+1（作为起点）、另一个顶点入度=出度+1（作为终点）、其他顶点出度=入度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Fleury : Graph
{
vector<int> vis, cur, p;
Fleury(int n) : Graph(n) {}
void dfs(int u)
{
for (int &i = cur[u], k; i < v[u].i.size(); ++i) //遍历原图的反向图，这里加了一个「当前弧」优化
if (k = v[u].i[i], !vis[k] && !vis[k ^ 1]) //无向图需要同时检查反向边未被访问过
{
vis[k] = 1;
dfs(e[k].first);
p.push_back(k);
}
}
void ask() //查询欧拉回路，路径上边的序号按顺序存在p中
{
vis.assign(e.size(), 0), cur.assign(v.size(), 0), p.clear();
for (int i = 0; i < v.size(); ++i)
if (v[i].i.size() % 2)
return dfs(i);
dfs(0);
}
};
混合图欧拉回路判定
首先给无向边随便定一个方向，设$\deg x$为 x 连出去的边数 − 连入 x 的边数。若存在$\deg x$为奇数，或者图不连通，则无解。否则建立源点 S，汇点 T。对于一个点 x，若$\deg x>0$，则 S 向 x 连边，容量$\frac{\deg x}{2}$；若$\deg x<0$，则 x 向 T 连边，容量$-\frac{\deg x}{2}$。 对于一条定了向的无向边$x\to y$，x 向 y 连边，容量 1，求出最大流，若与 S 和 T 连的每条边都满流，则有解。
连通性
无向图求割和双连通分量
- 割边：在连通图中，删除了连通图的某条边后，图不再连通。这样的边被称为割边，也叫做桥。
- 割点：在连通图中，删除了连通图的某个点以及与这个点相连的边后，图不再连通。这样的点被称为割点。构造 dfs 搜索树，在树上有两类节点可以成为割点：
- 对根节点 u，若其有两棵或两棵以上的子树，则该根结点 u 为割点；
- 对非根非叶节点 u，若其中的某棵子树的节点均没有指向 u 的祖先节点的回边，说明删除 u 之后，根结点与该棵子树的节点不再连通；则节点 u 为割点。
对于一个无向图的子图，当删除其中任意一条边后，不改变图内点的连通性，这样的子图叫做边的双连通子图。而当子图的边数达到最大时，叫做边的双连通分量。原理是图中所有割边再求一次 SCC，可直接使用求 SCC 的代码。
对于一个无向图的子图，当删除其中任意一个点后，不改变图内点的连通性，这样的子图叫做点的双连通子图。而当子图的边数达到最大时，叫做点的双连通分量。下面给出求点双连通分量的代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
struct BiconnectedConnectedComponenet : Graph
{
vector<int> dep, bid, stak, cutPoint, cutEdge; //bid边的端点所属双连通块
BiconnectedConnectedComponenet(int n) : Graph(n) {}
void ask()
{
dep.assign(v.size(), v.size());
bid.assign(e.size(), e.size());
cutPoint.assign(v.size(), 0);
cutEdge.assign(e.size(), 0);
for (int i = 0; i < v.size(); ++i)
if (dep[i] == v.size())
dfs(i, v.size());
}
int dfs(int u, int fa)
{
int low = dep[u] = fa != v.size() ? dep[fa] + 1 : 0;
for (int i = 0, k, to, lowto; i < v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second, to != fa)
{
if (dep[to] == v.size())
{
stak.push_back(k);
low = min(low, lowto = dfs(to, u));
if (lowto > dep[u])
cutEdge[k] = cutEdge[k ^ 1] = 1;
if (lowto >= dep[u])
for (cutPoint[u] = fa != v.size() || i;;)
{
int x = stak.back();
stak.pop_back();
bid[x] = bid[x ^ 1] = k;
if (x == k)
break;
}
}
else if (dep[to] < dep[u])
{
stak.push_back(k);
low = min(low, dep[to]);
}
}
return low;
}
};
双连通图的构造
先求出所有的桥，然后删除这些桥边，剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点，再把桥边加回来，最后的这个图一定是一棵树，边连通度为 1。统计出树中度为 1 的节点的个数，即为叶节点的个数，记为leaf。至少在树上添加(leaf+1)/2条边，就能使树达到边双连通：先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的；然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。
无向图求边双连通分量&有向图求强连通分量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct StronglyConnectedComponenet : Graph
{
vector<int> dep, sid, stak; //sid=点所属连通块内一点
StronglyConnectedComponenet(int n) : Graph(n) {}
void ask()
{
dep.assign(v.size(), v.size());
sid.assign(v.size(), v.size());
for (int i = 0; i < v.size(); ++i)
if (dep[i] == v.size())
dfs(i, v.size());
}
int dfs(int u, int fa)
{
int low = dep[u] = fa != v.size() ? dep[fa] + 1 : 0;
stak.push_back(u);
for (int i = 0, k, to; i < v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second, to != fa /*, 1*/) //求强连通分量把注释去掉，即允许走回边
{
if (dep[to] == v.size())
low = min(low, dfs(to, u));
else if (sid[to] == v.size())
low = min(low, dep[to]);
}
if (low == dep[u])
for (;;)
{
int x = stak.back();
stak.pop_back();
sid[x] = u;
if (x == u)
break;
}
return low;
}
};
2-SAT
使用示例，n 个布尔变量$x_0\dots x_{n-1}$，逻辑表达式$Y=(A_0+B_0)(A_1+B_1)\dots(A_{m-1}+B_{m-1})$，其中$A_i,B_i\in\lbrace x_j,\overline{x_j}\rbrace $，判断是否存在$x_0\dots x_{n-1}$的取值使得 Y 值为 1。因为$A+B=(\overline A\to B)(\overline B\to A)$，所以对于一个要求$A+B$，我们连$\overline A\to B,\overline B\to A$两条边。如果有一条边$A\to B$，意味着如果 A 成立那么 B 必然成立。若$\exists i,x_i,\overline{x_i}\in$同一 SCC，则不存在。
模板要求顶点数v.size()是偶数，i与i ^ 1互为相反变量且奇数下标代表布尔变量为真的情况。最后输出结果在ok中。不满足对任意 iok[i] ^ ok[i ^ 1] == 1时，ask函数返回false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
struct TwoSat : StronglyConnectedComponenet
{
vector<int> ok;
TwoSat(int n) : StronglyConnectedComponenet(n) {}
void addOR(int a, int b) { add({a ^ 1, b}), add({b ^ 1, a}); }
void addXOR(int a, int b) { addOR(a, b), addOR(a ^ 1, b ^ 1); }
void addXNOR(int a, int b) { addOR(a, b ^ 1), addOR(a ^ 1, b); }
int ask()
{
StronglyConnectedComponenet::ask();
for (int i = 0; i < v.size(); i += 2)
if (sid[i] == sid[i ^ 1])
return 0;
vector<vector<int>> g(v.size());
vector<int> ind(v.size(), 0), cf(v.size(), 0), stak;
for (int i = 0; i < v.size(); ++i)
{
cf[sid[i]] = sid[i ^ 1];
for (int j = 0, k; j < v[i].o.size(); ++j)
if (sid[e[k = v[i].o[j]].second] != sid[i])
g[sid[e[k].second]].push_back(sid[i]), ++ind[sid[i]];
}
for (int i = 0; i < v.size(); ++i)
if (sid[i] == i && !ind[i])
stak.push_back(i);
for (ok.assign(v.size(), -1); !stak.empty();)
{
int u = stak.back();
stak.pop_back();
if (ok[u] < 0)
ok[u] = 1, ok[cf[u]] = 0;
for (int i = 0; i < g[u].size(); ++i)
if (!--ind[g[u][i]])
stak.push_back(g[u][i]);
}
for (int i = 0; i < v.size(); ++i)
if (i != sid[i])
ok[i] = ok[sid[i]];
return 1;
}
};
2-SAT 暴力搜索求字典序最小的解
使用示例，时间复杂度最坏为为$O(VE)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct TwoSat : Graph
{
vector<int> ok;
TwoSat(int n) : Graph(n) {}
void addOR(int a, int b) { add({a ^ 1, b}), add({b ^ 1, a}); }
void addXOR(int a, int b) { addOR(a, b), addOR(a ^ 1, b ^ 1); }
void addXNOR(int a, int b) { addOR(a, b ^ 1), addOR(a ^ 1, b); }
int dfs(int u, vector<int> &stak)
{
if (ok[u ^ 1])
return 0;
if (ok[u])
return 1;
ok[u] = 1;
stak.push_back(u);
for (int i = 0; i < v[u].o.size(); ++i)
if (!dfs(e[v[u].o[i]].second, stak))
return 0;
return 1;
}
int ask()
{
ok.assign(v.size(), 0);
for (int i = 0; i < v.size(); i += 2)
if (!ok[i] && !ok[i ^ 1])
{
vector<int> stak;
if (!dfs(i, stak))
{
for (int j = 0; j < stak.size(); ++j)
ok[stak[j]] = 0;
if (!dfs(i ^ 1, stak))
return 0;
}
}
return 1;
}
};
二分图
二分图的一个等价定义是：不含有含奇数条边的环的图。
完美匹配图中所有的顶点都是匹配点。
二分图的最小点覆盖（最小割）是指最少的顶点数使得二分图 G 中的每条边都至少与其中一个点相关联。二分图中，最小割=最大匹配。
二分图的最小边覆盖（最大独立集）是指用尽量少的不相交简单路径覆盖二分图中的所有顶点。二分图中，最小点覆盖+最小边覆盖=总点数。
Hall 定理：二分图中的两部分顶点组成的集合分别为 X,Y ，则有一组无公共点的边，一端恰好为组成 X 的点的充分必要条件是：X 中的任意 k 个点至少与 Y 中的 k 个点相邻。对于区间图只需要考虑极端情况，线段树维护。
关键点：一定在最大匹配中的点。 求出任意一个最大匹配，那么只需要考虑哪些匹配点不一定在。 假设是考虑左侧的点，右侧类似： 将匹配边从右往左，非匹配边从左到右，从左侧每个未匹配点开始 DFS 到的匹配点都不是关键点。
关键边：求出任意一个最大匹配，将匹配边从右到左，剩余边从左到右，求出 SCC。 对于一条边：若它位于当前匹配中，那么若两端点位于同一 SCC，则是可能在，否则必定在；若它不位于当前匹配中，那么若两端点位于同一 SCC，则是可能在，否则必定不在。
Hungary 求最大匹配
左边 nl 个点$0\dots nl-1$，右边 nr 个点$0\dots nr-1$，取n=max(nl,nr)，左 i 右 j 间相连则g[i].push_back(j);。
生成fl[i]表示左边第 i 个匹配右边第fl[i]个，fr同理。时间复杂度$O(n^3)$。未匹配的值为fl[i] == N。匹配是一个边集，其中任意两条边都没有公共顶点；扫一遍fl或fr判断有多少不等于N即为最大匹配数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Hungary
{
vector<int> g[N];
int n, fl[N], fr[N], vr[N];
int dfs(int x, int rt)
{
for (auto y : g[x])
if (vr[y] != rt)
if (vr[y] = rt, fr[y] == N || dfs(fr[y], rt))
return fl[fr[y] = x] = y, 1;
return 0;
}
void ask()
{
fill(fl, fl + n, N), fill(fr, fr + n, N), fill(vr, vr + n, N);
for (int i = 0; i < n; ++i)
if (fl[i] == N)
dfs(i, i); //找完全匹配时如果返回值为0可直接return
}
};
HopcroftKarp 求最大匹配
使用示例，时间复杂度$O(\sqrt{\vert V\vert }\vert E\vert )$，稀疏图上效果明显。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
struct HopcroftKarp
{
vector<int> g[N];
int n, fl[N], fr[N], hl[N], hr[N], q[N];
bool dfs(int x)
{
int c = hl[x] + 1, y = hl[x] = N;
for (auto y : g[x])
if (hr[y] == c)
if (hr[y] = N, fr[y] == N || dfs(fr[y]))
return fl[fr[y] = x] = y, 1;
return 0;
}
void ask()
{
fill(fl, fl + n, N), fill(fr, fr + n, N);
for (int x = 0; x < n; ++x)
for (auto y : g[x])
if (fr[y] == N)
{
fl[fr[y] = x] = y;
break;
}
for (int ql, qr, ok;;)
{
fill(hl, hl + n, N), fill(hr, hr + n, N);
for (int x = ql = qr = ok = 0; x < n; ++x)
if (fl[x] == N)
hl[q[qr++] = x] = 0;
while (ql < qr)
for (auto y : g[q[ql++]])
if (hr[y] == N)
{
hr[y] = hl[q[ql - 1]] + 1;
if (fr[y] == N)
ok = 1;
else if (hl[fr[y]] == N)
hl[q[qr++] = fr[y]] = hr[y] + 1;
}
if (!ok)
return;
for (int x = 0; x < n; ++x)
if (fl[x] == N)
dfs(x);
}
}
};
KuhnMunkres 求最优完备匹配
使用示例。
左 x 右 y 代价a[x][y]。最大费用流时，a 初始化 0；最大费用最大流时，a 初始化-N*INF。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
struct KuhnMunkres
{
ll a[N][N], hl[N], hr[N], slk[N];
int n, fl[N], fr[N], vl[N], vr[N], pre[N], q[N], ql, qr;
int check(int i)
{
if (vl[i] = 1, fl[i] != N)
return vr[q[qr++] = fl[i]] = 1;
while (i != N)
swap(i, fr[fl[i] = pre[i]]);
return 0;
}
void bfs(int s)
{
fill(slk, slk + n, INF), fill(vl, vl + n, 0), fill(vr, vr + n, 0);
for (vr[q[ql = 0] = s] = qr = 1;;)
{
for (ll d; ql < qr;)
for (int i = 0, j = q[ql++]; i < n; ++i)
if (!vl[i] && slk[i] >= (d = hl[i] + hr[j] - a[i][j]))
if (pre[i] = j, d)
slk[i] = d;
else if (!check(i))
return;
ll d = INF;
for (int i = 0; i < n; ++i)
if (!vl[i] && d > slk[i])
d = slk[i];
for (int i = 0; i < n; ++i)
{
if (vl[i])
hl[i] += d;
else
slk[i] -= d;
if (vr[i])
hr[i] -= d;
}
for (int i = 0; i < n; ++i)
if (!vl[i] && !slk[i] && !check(i))
return;
}
}
void ask()
{
fill(fl, fl + n, N), fill(fr, fr + n, N), fill(hr, hr + n, 0);
for (int i = 0; i < n; ++i)
hl[i] = *max_element(a[i], a[i] + n);
for (int j = 0; j < n; ++j)
bfs(j);
}
};
带花树
一般图最大匹配
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
struct Blossom : Graph
{
vector<int> f;
Blossom(int n) : Graph(n) {}
void ask()
{
f.assign(v.size(), v.size());
vector<int> vis(v.size());
for (int s = 0, cnt = vis.back(); s < v.size(); ++s)
if (f[s] == v.size())
{
UnionfindSet ufs(v.size());
vector<int> pre(v.size(), v.size()), flag(v.size(), 2);
for (deque<int> q(flag[s] = 1, s); !q.empty() && f[s] == v.size(); q.pop_front())
for (int i = 0, x = q.front(), y, a, b; i < v[x].o.size(); ++i)
if (y = e[v[x].o[i]].second, y != f[x] && flag[y] && ufs.ask(x) != ufs.ask(y))
{
if (flag[y] == 1)
{
for (a = x, b = y, ++cnt;; swap(a, b))
if (a != v.size())
{
if (vis[a = ufs.ask(a)] == cnt)
break;
vis[a] = cnt, a = f[a] != v.size() ? pre[f[a]] : v.size();
}
if (ufs.ask(x) != a)
pre[x] = y;
if (ufs.ask(y) != a)
pre[y] = x;
for (int p[2] = {x, y}, j = 0; j < 2; ++j)
for (int x = p[j], y, z; x != a; ufs.merge(y, x), ufs.merge(x = z, y))
{
if (ufs.ask(z = pre[y = f[x]]) != a)
pre[z] = y;
if (!flag[y])
flag[y] = 1, q.push_back(y);
if (!flag[z])
flag[z] = 1, q.push_back(z);
}
}
else if (f[y] != v.size())
pre[y] = x, flag[y] = 0, flag[f[y]] = 1, q.push_back(f[y]);
else
{
for (pre[y] = x; y != v.size();)
swap(y, f[f[y] = pre[y]]);
break;
}
}
}
}
};
树形图
最小生成树
无向图
同时给出 Prim 算法（生成新树）、Kruskal 算法（消耗小）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
struct Prim : Graph
{
struct DisGreater
{
bool operator()(const Edge &e1, const Edge &e2)
{
return e1.len > e2.len;
}
};
ll ans;
vector<int> vis;
priority_queue<Edge, vector<Edge>, DisGreater> q;
Prim(const Graph &g, int root) : Tree(n), ans(0), vis(g.v.size(), 0) //生成新树，每条边都要有等长反向边
{
for (insert(root, g); !q.empty();)
{
Edge ed = q.top();
if (q.pop(), !vis[ed.second])
insert(ed.second, g), ans += ed.len, add(ed);
}
}
void insert(int u, const Graph &g) //把点和对应的相连的边加入集合
{
vis[u] = 1;
for (int i = 0, k; i < g.v[u].o.size(); ++i)
if (k = g.v[u].o[i], !vis[g.e[k].second])
q.push(g.e[k]);
}
};
ll kruskal(vector<Edge> &e, int n) //会清空边集e，每条边被认作无向边
{
ll ret = 0;
UnionFindSet ufs(n);
for (sort(e.begin(), e.end(), DisGreater()); !e.empty(); e.pop_back())
if (ufs.fa(e.back().from) != ufs.fa(e.back().to))
{
ufs.merge(e.back().from, e.back().to);
ret += e.back().len;
}
return /*ufs.siz>1?INF:*/ ret; //视情况选择去注释
}
有向图
指定以 root 为根，如果没有限定根那么新建一个虚拟点作为根，向所有边连边长最大边长+1的边，在最后生成的图中去掉此边。时间复杂度$O(VE)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
ll zhuLiu(vector<Edge> &e, int root, int n) //不存在返回INF
{
for (ll ret = 0;;)
{
vector<ll> in(n, INF);
vector<int> pre(n, n);
for (int i = 0, to; i < e.size(); ++i)
{
if (e[i].first == (to = e[i].second))
swap(e[i--], e.back()), e.pop_back();
else if (in[to] > e[i].len)
in[to] = e[i].len, pre[to] = e[i].first;
}
for (int i = in [root] = 0; i < n; ++i)
if (in[i] == INF)
return INF;
vector<int> id(n, n), vis(n, n);
int tn = 0;
for (int i = 0, v; i < n; ++i)
{
for (ret += in [v = i]; vis[v] != i && id[v] == n && v != root; v = pre[v])
vis[v] = i;
if (v != root && id[v] == n)
{
for (int u = pre[v]; u != v; u = pre[u])
id[u] = tn;
id[v] = tn++;
}
}
if (!tn)
return ret;
for (int i = 0; i < n; ++i)
if (id[i] == n)
id[i] = tn++;
for (int i = 0, v; i < e.size(); ++i)
if ((e[i].first = id[e[i].first]) != (e[i].second = id[v = e[i].second]))
e[i].len -= in[v];
n = tn, root = id[root];
}
}
树链剖分与 LCA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
struct Diagram : Graph
{
Fenwick data; //暂用树状数组作为默认数据结构
Diagram(const Graph &g, int root) : Graph(g.v.size()), data(g.v.size())
{
build(root, g);
int cnt = v[root].dfn = v[root].dep = 1;
dfs(v[root].top = root, cnt);
}
void build(int u, const Graph &g) //无向图dfs建树，且重边在最前，u为根节点
{
v[u].siz = 1;
for (int i = 0, k, to; i < g.v[u].o.size(); ++i)
if (k = g.v[u].o[i], to = g.e[k].second, !v[to].siz) //没访问过的点siz默认0
{
build(to, g);
v[u].siz += v[to].siz;
Graph::add(g.e[k]);
if (v[ch(u)].siz < v[to].siz) //重边移到最前
swap(v[u].o.front(), v[u].o.back());
}
}
void dfs(int u, int &cnt)
{
for (int i = 0, to; i < v[u].o.size(); ++i)
{
v[to = ch(u, i)].dfn = ++cnt;
v[to].top = i ? to : v[u].top;
v[to].dep = v[u].dep + 1;
dfs(to, cnt);
}
}
int lca(int x, int y)
{
for (; v[x].top != v[y].top; x = fa(v[x].top))
if (v[v[x].top].dep < v[v[y].top].dep)
swap(x, y);
if (v[x].dep < v[y].dep)
swap(x, y);
return y;
}
ll ask(int x, int y)
{
ll ans = 0;
for (; v[x].top != v[y].top; x = fa(v[x].top))
{
if (v[v[x].top].dep < v[v[y].top].dep)
swap(x, y);
ans += data.ask(v[v[x].top].dfn, v[x].dfn);
}
if (v[x].dep < v[y].dep)
swap(x, y);
return ans += data.ask(v[y].dfn, v[x].dfn);
}
void add(int x, int y, ll pv)
{
for (; v[x].top != v[y].top; x = fa(v[x].top))
{
if (v[v[x].top].dep < v[v[y].top].dep)
swap(x, y);
data.add(v[v[x].top].dfn, v[x].dfn, pv);
}
if (v[x].dep < v[y].dep)
swap(x, y);
data.add(v[y].dfn, v[x].dfn, pv);
}
};
点剖（点分治）
使用示例，零号点为虚节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct TreeDiv : Graph
{
int root;
vector<int> mx, siz, vis;
TreeDiv(int n) : Graph(n), mx(n, n), siz(n), vis(n) {}
void dfsRoot(int u, int fa)
{
for (int i = mx[u] = siz[u] = 0, k, to; i < v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second, to != fa && !vis[to])
if (dfsRoot(to, u), siz[u] += siz[to], mx[u] < siz[to])
mx[u] = siz[to];
if (mx[u] < mx[0] - ++siz[u])
mx[u] = mx[0] - siz[u];
if (mx[root] >= mx[u])
root = u;
}
void dfsDis(int u, int fa, ll d)
{
//用d更新答案
for (int i = 0, k, to; i < v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second, to != fa && !vis[to])
dfsDis(to, u, d + e[k].len);
}
int cal(int u, ll d) //返回符合要求的点对数
{
return dfsDis(u, 0, d), /*得到答案*/;
}
void dfs(int u = 1)
{
dfsRoot(u, root = 0), ans += cal(u = root, 0), vis[u] = 1;
for (int i = 0, k, to; i < v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second, !vis[to])
ans -= cal(to, e[k].len), mx[0] = siz[to], dfs(to);
}
};