前言：
$\qquad$ 图论的复习笔记，大体以模板为主。
$\qquad$ 这边 Latex 有点炸，原网址 https://xjx885.coding-pages.com/post/nEDVoSj5j/
$\qquad$ 建议与基础图论知识拓展 一起食用。
$~\\$
正文：
$\qquad$ 图：由若干给定点和连接这些点之间的边组成的图形。
$\qquad$ 图的存储：邻接表/邻接矩阵，我习惯直接上 vector。
$\qquad$ 图上搜索：在图上进行的 DFS/BFS，可以（在时间无限的前提下）解决绝大多数问题，是骗分的好方法。
$\qquad$ 应用：求连通块，求无权图最短路等，应用不多，大多数时候配合其它算法一起使用。
$\qquad$ 有向无环图（DAG）：没有环的有向图。
$\qquad$ 拓扑排序：对一张图上的节点按依赖关系排序的过程。
$\qquad$ 实现方法：求入度，找出入度为 $0$ 的点，拿出来放队列里，扫描队列，每扫到一个点，就把这个点连接的所有点入度 $-1$，如果入度为 $0$ 就往队列里放。队列中出现的节点的顺序就是拓扑排序后的顺序，如果有节点没入队，则图中有环。
$\qquad$ 应用：前面的点不依赖后面的点，故其排序结果可作为 DAG 上 DP 的递推顺序，有环图可先缩点再进行拓扑排序。
$~\\$
-
解析：题目保证了按所给边建出来的图是个 DAG，随便跑个拓扑排序就好了。设 $f(i)$ 表示以 $i$ 为终点最多能浏览多少城市，转移方程显然（方法不唯一，你要闲着无聊倒着来也是可以的）。
-
代码：
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read();
const int N = 1e5 + 10;
int n, m, ind[N], f[N];
queue <int > q;
vector <int > link[N];
void topo()
{
for(register int k = 1; k <= n; k++)
if(!ind[k]) q.push(k), f[k] = 1;
while(!q.empty())
{
int wz = q.front();
q.pop();
for(int k = 0; k < (int )link[wz].size(); k++)
{
int to = link[wz][k];
if(!(--ind[to])) q.push(to);
f[to] = max(f[to], f[wz] + 1);
}
}
}
signed main()
{
n = read(), m = read();
for(register int k = 1; k <= m; k++)
{
int u = read(), v = read();
link[u].push_back(v), ind[v]++;
}
topo();
for(register int k = 1; k <= n; k++)
printf("%d\n", f[k]);
return 0;
}
inline int read()
{
int fh = 1, x = 0, ch = '~';
while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();
return x * fh;
}
$~\\$
$~\\$
$\qquad$ 强连通：一张有向图 $G$ 强连通，意味着 $G$ 中任意两点都连通。
$\qquad$ 强连通子图：有一有向图 $G’ \subseteq G$，若 $G’$ 强连通，则 $G’$ 是 $G$ 的强连通子图。
$\qquad$ 强连通分量：极大的强连通子图。
$\qquad$ 强连通分量求法： Tarjan 算法。
$\qquad$ 实现：进行一种特殊的 DFS，如果在该 DFS 的过程中碰触到了特定节点，则从栈中找强连通分量（具体原理，实现方法不多讲，自行百度）。
$\qquad$ 代码：
void Tarjan(int wz)
{
dfn[wz] = low[wz] = ++tot;
in[wz] = 1, s.push(wz);
for(int k = 0; k < (int )link[wz].size(); k++)
{
int to = link[wz][k];
if(!dfn[to])
Tarjan(to), low[wz] = min(low[wz], low[to]);
else if(in[to])
low[wz] = min(low[wz], dfn[to]);
}
if(dfn[wz] == low[wz])
{
int p = ++color - 11451413;
while(!s.empty() && p != wz)
in[p = s.top()] = 0, col[p] = color, s.pop();
}
}
$\qquad$ 应用：单独应用很少，甚至拓展出的割点和桥的应用也不多，所以不讲。这里讲一下拓展出的可以和上面的拓扑排序结合的缩点算法。
$\qquad$ 对每个点跑一遍 tarjan 后，缩点操作变得很简单，如果原图中存在边 $(u,v)$，则将 $u$ 所在的连通块与 $v$ 所在的连通块在新图上连边。
$\qquad$ 注意两点：首先，如果 $u,v$ 在同一个连通块内，则它们之间不需连边（题目特别要求除外），其次，我们最好避免重边，避免重边有很多方法，我常用的一种是后面代码里面的，直接暴力地开个 $set$，这适用于边数不多的情况，还有一种是建一个 bitset，依次让每一个连通块向其他连通块建边，建边后再 bitset 中打上标记，换到下一个连通块时清空标记即可，这种方法在复杂度上比较优秀。
$\qquad$ 缩点完之后就成了 DAG 了，就可以跑 topo 解决很多问题了。
$~\\$
-
解析：本题其实没必要用 topo，直接判有多少点出度为零就行了，不过后面的代码还是用了 topo。大概讲一下 topo 的思路：令 $f(i)(j)$ 表示 $j$ 号点（缩点后） 是否喜欢 $i$ 号点，转移的时候合并数组，最后判数组中是不是全是一就行了， $j$ 这一维可以用 bitset 维护，很方便 。 注意：有一种思路是这样的： 设 $f(i)$ 表示喜欢 $i$ 号点的人数，转移时加在一起，最后判人数是不是等于总人数。这种方案在树上是可行的，但 DAG 上不可行，因为两个点之间的路径不一定唯一，所以可能有点被重复计算了。
-
代码：
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
inline int read();
using namespace std;
const int N = 1e4 + 10;
int n, m, tot, color;
int dfn[N], low[N], col[N], in[N];
vector <int > link[N];
stack <int > s;
bitset <N > f[N];
void Tarjan(int wz)
{
dfn[wz] = low[wz] = ++tot;
in[wz] = 1, s.push(wz);
for(int k = 0; k < (int )link[wz].size(); k++)
{
int to = link[wz][k];
if(!dfn[to])
Tarjan(to), low[wz] = min(low[wz], low[to]);
else if(in[to])
low[wz] = min(low[wz], dfn[to]);
}
if(dfn[wz] == low[wz])
{
int p = ++color - 11451413;
while(!s.empty() && p != wz)
in[p = s.top()] = 0, col[p] = color, s.pop();
}
}
vector <int > new_link[N];
queue <int > q;
int ind[N], ans;
set <pair <int , int > > built;
void topo()
{
for(int k = 1; k <= color; k++) f[k][k] = 1;
for(int k = 1; k <= color; k++) if(!ind[k]) q.push(k);
while(!q.empty())
{
int wz = q.front();
q.pop();
for(int k = 0; k < (int )new_link[wz].size(); k++)
{
int to = new_link[wz][k];
if(!(--ind[to])) q.push(to);
f[to] |= f[wz];
}
}
}
signed main()
{
n = read(), m = read();
for(register int k = 1; k <= m; k++)
{
int u = read(), v = read();
link[u].push_back(v);
}
for(register int k = 1; k <= n; k++)
if(!dfn[k]) Tarjan(k);
for(register int k = 1; k <= n; k++)
for(int i = 0; i < (int )link[k].size(); i++)
{
int to = link[k][i];
if(col[k] != col[to] && !built.count(make_pair(col[k], col[to])))
new_link[col[k]].push_back(col[to]), ind[col[to]]++, built.insert(make_pair(col[k], col[to]));
}
topo();
for(register int k = 1; k <= color; k++) f[0][k] = 1;
for(register int k = 1; k <= n; k++)
if(f[col[k]] == f[0]) ans++;
printf("%d\n", ans);
return 0;
}
inline int read()
{
int fh = 1, x = 0, ch = '~';
while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();
return x * fh;
}
$~\\$
$\qquad$ 生成树： 取图中边集 $E’$ ，使得图中点集 $P$ 连通，且二者组成的新图 $G’$ 是一棵树，这棵新树是图 $G$ 的一种生成树。
$\qquad$ 最小生成树： $E’$ 的权值和最小的生成树。
$\qquad$ 算法：Kruskal 算法。（其它几个算法不咋常用，略过）
$\qquad$ 实现：把 $E$ 中所有边按权值排序，从小到大依次拿边，如果边两端未连通，则将该边计入答案，并连通两端，否则跳过。维护两个点之间是否连通可以使用并查集。
$~\\$
- 代码：
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e3 + 10;
const int M = 2e5 + 10;
int n, m, tot, ans, fa[N];
int find (int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
struct node
{
int a, b, c;
bool operator < (const node & other) const
{
return c < other.c;
}
} edge[M];
inline int read();
signed main()
{
n = read(), m = read();
for(register int k = 1; k <= n; k++)
fa[k] = k;
for(register int k = 1; k <= m; k++)
edge[k].a = read(), edge[k].b = read(), edge[k].c = read();
sort(edge + 1, edge + 1 + m);
for(register int k = 1; k <= m; k++)
{
if(tot == n - 1) break;
int a = edge[k].a, b = edge[k].b, c = edge[k].c;
if(find(a) != find(b))
ans += c, fa[fa[a]] = fa[b], tot++;
}
if(tot == n - 1) printf("%d\n", ans);
else puts("orz");
return 0;
}
inline int read()
{
int fh = 1, x = 0, ch = '~';
while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();
return x * fh;
}
$~\\$
$\qquad$ 最小生成树也很少单独考，主要还是和其它图论知识点混在一起丢给考生。
$\qquad$ 拓展： 次小生成树和严格次小生成树，思路是一样的：先跑出最小生成树，然后遍历所有未被选中的边 $(u,v,d)$ ，用倍增跑出树上 $u,v$ 之间的最长边（严格次小生成树还要严格次小边），然后拿枚举的边替换跑出来的边就好，取权值总和最小值。
$\qquad$ 代码不放了，没啥难度的操作，但是码量还是有的（尤其是严格次小生成树）。
$~\\$
$\qquad$ 最短路：从 $E$ 中选取一条路径 $R$ 使 $u,v$ 两点连通，求 $R$ 最小边权和。
$\qquad$ 算法： Floyd，SPFA，Dijkstra 。
$\qquad$ Floyd 主要用于求任意两点间的最短路，复杂度 $O(n^3)$。
$\qquad$ SPFA 可以用在稀疏图上，稠密图一般也可以，复杂度玄学，上界为 $O(nm)$。
$\qquad$ Dij 只能用在正权图上，可并堆优化后复杂度是稳定的 $O(nlogn)$。
$\qquad$ 下面只放模板，扩展可以看我的另一篇博文：基础图论知识拓展。
$~\\$
- 例题：洛谷 P1359 租用游艇。
- 代码：
// Floyd
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read();
const int N = 210;
int n, f[N][N];
signed main()
{
n = read();
memset(f, 0x3f, sizeof(f));
for(register int k = 1; k <= n; k++)
for(int i = k + 1; i <= n; i++)
f[k][i] = read();
for(register int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(k != i && i != j && k != j)
if(f[i][k] + f[k][j] < f[i][j])
f[i][j] = f[i][k] + f[k][j];
printf("%d", f[1][n]);
return 0;
}
inline int read()
{
int fh = 1, x = 0, ch = '~';
while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();
return x * fh;
}
$~\\$
// SPFA
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read();
const int N = 210;
queue <int > q;
int n, dis[N], in[N];
struct node
{
int to, len;
node (int a, int b)
{
to = a, len = b;
}
node () { }
};
vector <node > link[N];
void SPFA()
{
memset(dis, 0x3f, sizeof(dis));
q.push(1), in[1] = 1, dis[1] = 0;
while(!q.empty())
{
int wz = q.front();
q.pop(), in[wz] = 0;
for(int k = 0; k < (int )link[wz].size(); k++)
{
int to = link[wz][k].to;
int len = link[wz][k].len;
if(dis[wz] + len < dis[to])
{
dis[to] = dis[wz] + len;
if(!in[to]) in[to] = 1, q.push(to);
}
}
}
}
signed main()
{
n = read();
for(register int k = 1; k <= n; k++)
for(int i = k + 1; i <= n; i++)
{
int x = read();
link[k].push_back(node(i, x));
}
SPFA(), printf("%d\n", dis[n]);
return 0;
}
inline int read()
{
int fh = 1, x = 0, ch = '~';
while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();
return x * fh;
}
$~\\$
// Dij
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read();
const int N = 210;
#define mp make_pair
#define P pair<int ,int >
priority_queue <P, vector <P>, greater<P> > q;
int n, dis[N], sol[N];
struct node
{
int to, len;
node (int a, int b)
{
to = a, len = b;
}
node () { }
};
vector <node > link[N];
void dij()
{
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0, sol[1] = 0, q.push(mp(0, 1));
while(!q.empty())
{
int wz = q.top().second;
q.pop();
if(sol[wz]) continue;
sol[wz] = 1;
for(int k = 0; k < (int )link[wz].size(); k++)
{
int to = link[wz][k].to;
int len = link[wz][k].len;
if(dis[wz] + len < dis[to])
{
dis[to] = dis[wz] + len;
q.push(mp(dis[to], to));
}
}
}
}
signed main()
{
n = read();
for(register int k = 1; k <= n; k++)
for(int i = k + 1; i <= n; i++)
{
int x = read();
link[k].push_back(node(i, x));
}
dij(), printf("%d\n", dis[n]);
return 0;
}
inline int read()
{
int fh = 1, x = 0, ch = '~';
while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();
return x * fh;
}
$~\\$
$\qquad$ 欧拉通路：通过图中所有边恰一次并经过所有顶点的通路。
$\qquad$ 欧拉回路：通过图中所有边恰一次并经过所有顶点并回到起点的通路。
$\qquad$ 简单的说，欧拉通路是一笔画，欧拉回路要求你一笔画完之后还能回到起点。
$\qquad$ 有欧拉通路的无向图叫半欧拉图，有欧拉回路的无向图叫欧拉图。
$\qquad$ 性质： $G$ 是欧拉图等价于 $G$ 没有奇度顶点。 $G$ 是半欧拉图等价于 $G$ 仅有 2 奇度顶点。
$\qquad$ 没啥大用…不放解法和例题了，有兴趣可以去 OI-wiki 上看。
$~\\$
$\qquad$ 差分约束系统：由 $m$ 个形如 $x_i-x_j\le c_k$ 的不等式组成的 $n$ 元一次不等式组，例如下面这个。
$$x1-x2\le 1$$
$$x2-x3\le 4$$
$$x3-x4\le 2$$
$\qquad$ $x1-x4$ 最大值怎么求？很简单，全部加起来就完了…但如果中间某些式子的形式变一下，并且式子变得很多呢？让电脑去移项转换？
$\qquad$ 不需要那么麻烦，我们观察式子的形式： $x_i-x_j\le c_k$，形似我们最短路中的 $dis_i-dis_j \le len(i,j)$。
$\qquad$ 所以我们可以通过最短路的松弛操作解决差分约束问题，具体方案是：如果我们要求 $x_n-x_1$ 的最大值，就把式子整理成 $x_j-x_i\le k$ 的形式，从 $i$ 向 $j$ 连边权为 $k$ 的边，跑最短路，如果我们要求 $x_n-x_1$ 的最小值，就把式子整理成 $x_j-x_i \ge k$ 的形式，从 $i$ 向 $j$ 连边权为 $k$ 的边，跑最长路。
$\qquad$ 如果最短路/最长路有负环/正环，则结果不存在，若 $1,n$ 不连通，则结果为无穷小/大。
$\qquad$ 注意：小于号要通过减一换成小于等于，大于号要同样换成大于等于，等于号可以换成两个式子，一个大于等于，一个小于等于。
$~\\$
- 例题：洛谷 P1250 种树。
-
解析：模板题，照着上面说的建边跑最SPFA就好，注意：题目还有隐含不等式，任意两点间最多只能种一棵树，最少要种零棵树。
-
代码：
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read();
const int N = 3e4 + 10;
struct node
{
int to, len;
node (int a, int b)
{
to = a, len = b;
}
node () { }
};
vector <node > link[N];
void add_edge(int u, int v, int w)
{
link[v].push_back(node(u, w));
}
int n, m, dis[N], in[N];
queue <int > q;
void SPFA()
{
memset(dis, 0xef, sizeof(dis));
q.push(0), in[0] = 1, dis[0] = 0;
while(!q.empty())
{
int wz = q.front();
q.pop(), in[wz] = 0;
for(int k = 0; k < (int )link[wz].size(); k++)
{
int to = link[wz][k].to;
int len = link[wz][k].len;
if(dis[wz] + len > dis[to])
{
dis[to] = dis[wz] + len;
if(!in[to]) q.push(to), in[to] = 1;
}
}
}
}
signed main()
{
n = read(), m = read();
for(register int k = 1; k <= n; k++)
add_edge(k - 1, k, -1);
for(register int k = 1; k <= n; k++)
add_edge(k, k - 1, 0);
for(register int k = 1; k <= m; k++)
{
int u = read(), v = read(), w = read();
add_edge(v, u - 1, w);
}
SPFA(), printf("%d", dis[n]);
return 0;
}
inline int read()
{
int fh = 1, x = 0, ch = '~';
while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();
return x * fh;
}
$~\\$
$\qquad$ 2-SAT 问题：给出 $n$ 个二元组和若干矛盾信息 $(x_i,y_j)$，求从每个二元组中选一个元素且选出元素互不矛盾的方案。
$\qquad$ 解决方案：以两组二元组 $(x_1,y_1),(x_2,y_2)$ 为例，若 $x_1$ 与 $y_1$ 矛盾，则选了 $x_1$ 就必须选 $y_2$，选了 $y_1$ 就必须选 $x_2$，其它元素间没有确定关系。
$\qquad$ 我们把各个元素抽象成点，把元素间这种“选了我就必须选他” 的关系视作有向边，则一个 2-SAT 问题被抽象成了一张有向图，我们可以对有向图进行缩点，一个强连通分量内的点必定一起选，若一个二元组的两个元素在同一个强连通分量内，则该 2-SAT 无解，否则有解。缩点后生成一张 DAG，对于一条有向边 $(u,v)$，若选 $u$ 则必选 $v$，若选 $v$ 则不一定选 $u$，所以如果一个二元组的两个点可达，则 “在前面（$u$）” 的点一定不选，而所谓 “在前面”，表现为拓扑序更小，也就是说拓扑序小的节点不选。如果两个点不可达？那就随便选好了。
$\qquad$ 所以整体思路是缩点+topo，但实际上不需要 topo，tarjan 求出来的连通块编号（我代码中的 $col$）本质上就是一个反拓扑序，所以可以直接代替 topo 序使用（其实不用管是什么序的，先随便打个大于号，如果答案反了就改成小于号就好）。
-
解析：把一个变量的真假看做二元组的两个元素，套板子即可。
-
代码：
#include <stack>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e6 + 10;
int n, m, color, tot;
int dfn[N], low[N], col[N], in[N];
vector <int > link[N];
stack <int > s;
void tarjan(int wz)
{
dfn[wz] = low[wz] = ++tot;
in[wz] = 1, s.push(wz);
for(int k = 0; k < (int )link[wz].size(); k++)
{
int to = link[wz][k];
if(!dfn[to])
tarjan(to), low[wz] = min(low[wz], low[to]);
else if(in[to])
low[wz] = min(low[wz], dfn[to]);
}
if(dfn[wz] == low[wz])
{
int t = ++color - 114514191;
while(!s.empty() && t != wz)
t = s.top(), s.pop(), col[t] = color, in[t] = 0;
}
}
inline int read();
signed main()
{
n = read(), m = read();
for(register int k = 1; k <= m; k++)
{
int i = read(), a = read(), j = read(), b = read();
link[i + (a ^ 1)*n].push_back(j + b * n);
link[j + (b ^ 1)*n].push_back(i + a * n);
}
for(register int k = 1; k <= 2 * n; k++)
if(!dfn[k]) tarjan(k);
for(register int k = 1; k <= n; k++)
if(col[k] == col[k + n])
{
puts("IMPOSSIBLE");
return 0;
}
puts("POSSIBLE");
for(register int k = 1; k <= n; k++)
if(col[k] > col[k + n]) printf("1 ");
else printf("0 ");
return 0;
}
inline int read()
{
int fh = 1, x = 0, ch = '~';
while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();
return x * fh;
}
$~\\$
$~\\$
结语：
$\qquad$ 考 CSP 时的 RP 已经够烂了，省选 RP 总该高一点吧。
省选加油啊！ ! 我们省选取消了 55555