小明の雜貨鋪

Strongly Connected Components 强连通分量 对于有向图，它是 强连通 的当且仅当其上每两个顶点都相互可达。 强连通分量 (Strongly Connected Components) 有向图的极大的强连通子图（把图划分为若干个强连通分量后，不存在两个强连通分量相互可达）。 DFS traversal of a Tree 树的 DFS 生成树 DFS 生成树 每当通过某条边访问到一个新节点，就加入这个点和这条边，并为点记录 DFS 序（unix 时间戳）。 DFS 生成树的边的种类： 树边 DFS 生成树上的边； 前向边 从某个点到它的某个子孙节点的边，产生了捷径。 反向边 从某个点到它的某个祖先节点的边，产生了环； 横叉边 从某个点到一个既非它子孙节点、也非它祖先节点的边，连接了两个强连通子图。 Tarjan Algorithm 肽键算法 反向边和横叉边起点的 DFS 序必然大于终点的 DFS 序，因此对于每个强连通分量，存在一个点是其他所有点的祖先。 引入如下数组： dfn[u] uuu 的 DFS 序。 low[u] uuu 所在子树...

稠密图 Input Output 40 2 2 32 0 4 82 4 0 33 8 3 0 7 Prim：从任意一个点开始，每次选择一个与当前点相邻且边权最小的点，并将两顶点之间的边加入到树中。时间复杂度 Θ(n2)\Theta(n^2)Θ(n2)，空间复杂度 Θ(n)\Theta(n)Θ(n)。 1234567891011121314151617vector<int> mn(n, inf), vis(n);mn[0] = 0;int ans = 0;for (int t = 0; t < n; ++t) { int u = -1; for (int j = 0; j < n; j++) { if (!vis[j] && (u == -1 || mn[j] < mn[u])) { u = j; } } vis[u] = 1; ans += mn[u]; for (int v...

并查集——转化为树 + 边 基环树的最大独立集 砍掉一条边 ststst 后是树，求树的最大独立集，但有限制 s,ts,ts,t 不能同时选。因此以 s,ts,ts,t 分别为根，求根节点不选的最大独立集。答案为两者较大的。对于基环树森林，对每个基环树分别处理。(洛谷 P2607 骑士) 123456789101112131415161718192021222324252627282930313233343536int n;cin >> n;vector<int> w(n);DSU dsu(n);vector<pair<int, int>> nte; // none-tree edgevector<vector<int>> E(n);for (int i = 0; i < n; i++) { int u, v; cin >> u >> v >> w[i]; cin >> v; v--; if...

一笔画问题，也被称为欧拉路径定理或七桥问题。 欧拉通路 通过图中每条边恰好一次的通路 欧拉回路 通过图中每条边恰好一次的回路，即起点与终点相同的欧拉通路 欧拉图 具有欧拉回路的图 半欧拉图 具有欧拉通路但不具有欧拉回路的图 有向欧拉图 有向图是欧拉图当且仅当： 非零度顶点是强连通的 每个顶点的入度和出度相等 有向图是半欧拉图当且仅当： 非零度顶点是弱连通的 至多一个顶点的出度与入度之差为 1 至多一个顶点的入度与出度之差为 1 其他顶点的入度和出度相等 用 Hierholzer 算法找出一条欧拉 (回) 路，时间复杂度 Θ(n+m)\Theta(n+m)Θ(n+m)，如果需要输出字典序最小的欧拉 (回) 路，则是 Θ(n+mlog⁡m)\Theta(n+m\log m)Θ(n+mlogm) 的。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849int n, m;cin >> n >>...

二分图 中的点由两个集合组成，且两个集合内部没有边。 二分图的判定 方法 1 (Backtracking algorithm m coloring problem)：等对图中的点染色，使每条边的两端点异色。(VJspr7A - 封锁阳光大学 ) 如果两个集合中的点分别染成黑色和白色，二分图中的每一条边都一定是连接一个黑色点和一个白色点。 Input Output 3 31 21 32 3 No 3 21 22 3 Yes 12345678910111213141516171819bool bipartite = true;vector<int> c(n, -1);c[0] = 0;queue<int> Q;Q.push(0);while (!Q.empty()) { int u = Q.front(); Q.pop(); for (auto& v : E[u]) { if (c[v] == -1) { c[v] = 1 ^...

单源最短路 正权图 朴素 Dijkstra Θ(n2)\Theta(n^2)Θ(n2) 优化 Dijkstra Θ(mlog⁡m)\Theta(m\log m)Θ(mlogm) 负权图 Bellman - Ford Θ(nm)\Theta(nm)Θ(nm) SPFA Θ(nm)\Theta(nm)Θ(nm) 多源最短路 负权图 Johnson Θ(nmlog⁡m)\Theta(nm\log m)Θ(nmlogm) Floyd Θ(n3)\Theta(n^3)Θ(n3) 正权图的单源最短路 Input Output 4 6 1 4 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4 0 2 4 31 1 1 14<-2<-1 稠密图——朴素 Dijkstra 从未确定最短路的点中选取最短路长度最小的点，为未确定最短路的点松弛出边，即 dv=min⁡{dv, du+wuv}d_v=\min\left\lbrace d_v,\...

二分图 Stop the Castle There are n castles and m obstacles on a chessboard. Each castle or obstacle occupies exactly one cell and all occupied cells are distinct. Two castles can attack each other, if they’re on the same row or the same column, and there are no obstacles or other castles between them. Find a way to place the minimum number of additional obstacles onto the chessboard, so that no two castles can attack each...

转化为树——树边和非树边 回忆 Tarjan 里讲的有向图 DFS 生成树： DFS 生成树 每当通过某条边访问到一个新节点，就加入这个点和这条边，并为点记录 DFS 序（unix 时间戳）。 DFS 生成树的边的种类： 树边 DFS 生成树上的边； 前向边 从某个点到它的某个子孙节点的边，产生了捷径。 反向边 从某个点到它的某个祖先节点的边，产生了环； 横叉边 从某个点到一个既非它子孙节点、也非它祖先节点的边，连接了两个强连通子图。 对于无向图是类似的，不同点是 无向图的 DFS 树没有横叉边 ，只有前向边和反向边，而前向边都是已访问的，可以认为 无向图的 DFS 树只有反向边，因此非树边的端点 u,vu,vu,v 的 LCA 为 vvv，作树上差分时，直接 wv−d, wu+dw_{v}-d,\ w_{u}+dwv​−d, wu​+d 即可。 删边后的连通性 给定一个无向连通图。每次询问给出一组边，确定删除这些边后图是否连通。 令第 iii 条非树边的权值是 2i2^i2i，再令这条边的两个端点在树上的对应路径上的边全部 ⊕2i\oplus...

12345678910111213141516171819202122232425262728293031323334353637383940414243444546/** 一维前缀和 **/vector<ll> pre(n + 1);for (int i = 0; i < n; i++) { pre[i + 1] = pre[i] + a[i];}// 查询 [l, r)auto get = [&](int l, int r) { return pre[r] - pre[l];};/** 二维前缀和 **/vector s(m + 1, vector<ll>(n + 1));for (int x = 0; x < m; x++) { for (int y = 0; y < n; y++) { s[x + 1][y + 1] = s[x + 1][y] + s[x][y + 1] - s[x][y] + a[x][y]; }}//...

在一个有向图上选择一个 源点 (s)，一个 汇点 (t)，每一条边上都有一个流量上限（以下称为 容量 ©），即经过这条边的流量不能超过这个上界，同时，除源点和汇点外，所有点的入流和出流都 相等，而源点只有流出的流，汇点只有汇入的流。 最大流（Max-flow） 使得流的值最大的流函数被称为网络的最大流 , 此时的 流的值被称为网络的最大流量。 Ford-Fulkerson Algorithm 一句话概括：添加反向边使流量可以回退。 共有 mmm 条边，最大流量为 fff ，每一次循环至少会让最大流增大一份，故时间复杂度最坏情况下为 O(f⋅m)O(f·m)O(f⋅m)。 Edmonds-Karp Algorithm 为对 FF 的优化：在寻找简单路径时将图视为边权为 1 的无向图并对其跑最短路，即 BFS。（这里也可以理解为 EK 算法是 FF 算法的一种实现，因为 FF 算法并没有对路径选择有任何约束。） 共有 nnn 个点，mmm 条边时，残余图最多有 mmm 条反向边总共 2⋅m2·m2⋅m 条边，每一轮最短路需要 O(m)O(m)O(m)，最多循环...