小明の雜貨鋪

头文件和常用函数 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include <bits/stdc++.h>using namespace std;using ll = long long;using i128 = __int128;#define int llinline ll read() { ll x = 0, f = 0; char c = getchar(); while (c > 57 || c < 48) f |= c == 45, c = getchar(); while (c <= 57 && c >= 48) x = (x << 3) + (x << 1) + c - 48, c = getchar(); return f ? -x : x;}ll...

2025 年 1 月 24 日版 基础算法 数据结构 图论 图论 - 树 计算几何 数学 字符串 题解 快读 .category-navigation { width: 100%; margin: 0 auto; padding: 20px; } .main-categories { display: flex; justify-content: center; gap: 20px; margin-bottom: 30px; flex-wrap: wrap; } .category-btn { padding: 12px 24px; font-size: 16px; border: none; border-radius: 8px; background-color: #f0f0f0; cursor: pointer; transition:...

12345678910111213141516171819202122232425262728293031323334353637383940414243struct TwoSat { int n; vector<vector<int>> E; vertor<int> ans; TwoSat(int n) : n(n), E(2 * n), ans(n) {} void add(int u, bool f, int v, bool g) { E[2 * u + !f].push_back(2 * v + g); E[2 * v + !g].push_back(2 * u + f); } bool satisfiable() { vector<int> id(2 * n, -1), dfn(2 * n, -1), low(2 * n, -1); vector<int> stk; int unix = 0, cnt =...

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 所在子树...

二分图 中的点由两个集合组成，且两个集合内部没有边。 二分图的判定 方法 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 ^...

一笔画问题，也被称为欧拉路径定理或七桥问题。 欧拉通路 通过图中每条边恰好一次的通路 欧拉回路 通过图中每条边恰好一次的回路，即起点与终点相同的欧拉通路 欧拉图 具有欧拉回路的图 半欧拉图 具有欧拉通路但不具有欧拉回路的图 有向欧拉图 有向图是欧拉图当且仅当： 非零度顶点是强连通的 每个顶点的入度和出度相等 有向图是半欧拉图当且仅当： 非零度顶点是弱连通的 至多一个顶点的出度与入度之差为 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 >>...

Edge Biconnected Components 边双连通分量 & 割与割边缩点 在一张连通的无向图中，称 uuu 和 vvv 边双连通 ，如果无论删去哪条 边 都 不能 使它们 不连通。 边双连通具有传递性，即若 x,yx,yx,y 边双连通，y,zy,zy,z 边双连通，则 x,zx,zx,z 边双连通。 边双连通分量缩点后是一棵树。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465struct EBCC { int n, unix, tot; vector<vector<pair<int, int>>> E; vector<int> dfn, low, bel, stk; EBCC(int n) : n(n), unix(0), tot(0), E(n), dfn(n,...

并查集——转化为树 + 边 基环树的最大独立集 砍掉一条边 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...

稠密图 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...

二分图 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...