小明の雜貨鋪

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

转化为树——树边和非树边 回忆 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...

二叉树 先序遍历：先遍历根节点，然后遍历左节点，最后遍历右节点 中序遍历：先遍历左节点，然后遍历根节点，最后遍历右节点（大概可以理解为把树平面投影至二维从左到右） 后序遍历：先遍历左节点，然后遍历右节点，最后遍历根节点 树上差分 Adjacent Difference on Tree 问题 每次操作将树上 u→vu\to vu→v 路径上的所有点权增加 ddd，求每个点的点权。 思路 用类似前缀和的思想存储树上的点权。用 val[p] 存储 ppp 节点上方的点权增加值，对于上述操作，按差分思想，只需 12val[u] += d; val[v] += d;val[lca(u,v)] -= d; val[p[lca(u,v)] -= d; 复原时，从根节点开始一步步累加。 1234567void dfs2(int u, int p = 0) { for (auto& v : E[u]) { if (v == p) continue; dfs2(v, u); val[u]...

单源最短路 正权图 朴素 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,\...

P2756 飞行员配对方案问题 P2756 飞行员配对方案问题 - 洛谷 二分图最大匹配，用最大流跑也没问题 1234567891011121314151617181920212223242526272829signed main(){ int n, m; cin >> m >> n; MaxFlow maxflow(n + 5); int s = n + 1; int t = n + 2; for(int i = 1; i <= m; i++){ maxflow.add(s, i, 1); } for(int i = m + 1; i <= n; i++){ maxflow.add(i, t, 1); } int u, v; while(cin >> u >> v){ if(u == -1 && v == -1)break; ...

在树上，我们可以任选一个节点作为根节点，从而定义出每个节点的深度和每棵子树的根。 在 DP 的状态表示中，第一维通常是节点编号，第二维代表状态基 。大多数时候，我们采用 递归 的方式实现树形动态规划。对于每一个节点 xxx，先递归它的每一个子节点上进行 DP ，在 回溯时，从子节点向节点 xxx 进行状态转移。 有根树的树形 DP 树背包 有根树，有点权。mmm 元点集 SSS 满足：若子节点 ∈S\in S∈S，则父节点 ∈S\in S∈S。最大化 SSS 点权和。 123456789101112int n, m, w[N], dp[N][M];auto dfs = [&](this auto&& dfs, int u) -> void { dp[u][1] = w[u]; for (auto& v : E[u]) { dfs(v); for (int k = m; k >= 1; --k) { for (int i = k; i...

在一个有向图上选择一个 源点 (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)，最多循环...

树链剖分 把一棵树分割成若干条链，以便于维护（路径、子树）信息。 重链剖分 重链剖分 (Heavy Path Decomposition) 从树上每个 轻节点 出发，不断向下走 重边，构成一条链。任意点恰好在一条重链中。任意点到根的路径为 Θ(log⁡n)\Theta(\log n)Θ(logn) 条重链和轻边交替形成。 使用两次 DFS 完成重链剖分，时空复杂度 Θ(n)\Theta(n)Θ(n)。 若 u,vu,vu,v 在同一条链上，LCA 是深度较小的那个节点；否则，将链头深度较大的节点跳转到其链头的父节点上，直至两点在同一条链上。复杂度 Θ(n)−Θ(log⁡n)\Theta(n) - \Theta(\log n)Θ(n)−Θ(logn)。 回忆 树的 DFS 序：每个节点在 DFS 中的进出栈的时间序列。每棵子树的 DFS 序都是连续的，且子树上根节点 DFS 序最小；而且，如果优先遍历重子节点，那么同一条链上的节点的 DFS 序也是连续的，且链头节点 DFS 序最小。因此，uuu 的子树上所有节点的编号介于 dfsn[u] 和 dfsnR[u] 之间，其中...

树的重心 树的重心要么 惟一 ，要么 有两个，且这两个重心相邻。 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半，即 siz[v] * 2 < siz[u]。 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。 求树的重心 1234567891011121314151617vector<int> siz(n), mss(n); // 固定根时的子树大小 最大子树大小auto dfs = [&](this auto&& dfs, int u, int p) -> void { siz[u] = 1; for (auto v : E[u]) { if (v == p) continue; dfs(v, u); siz[u] += siz[v];...