小明の雜貨鋪

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

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

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

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

multiset 的 maintain 法 枚举左端点，使用大小根堆 maintain 求出所有右端点的答案。时间复杂度 Θ(n2log⁡n)\Theta(n^{2}\log n)Θ(n2logn)。 例 1 求 {a}\lbrace a \rbrace{a} 的所有子序列的中位数，数据范围：n⩽2000, 0⩽ai⩽109n \leqslant 2000,\ 0 \leqslant a_{i} \leqslant 10^{9}n⩽2000, 0⩽ai​⩽109。 12345678910111213141516171819202122int n = read();for (int i = 1; i <= n; i++) a[i] = read();for (int i = 1; i <= n; i++) { priority_queue<int, vector<int>> L; priority_queue<int, vector<int>, greater<>> R; int mid =...

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

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

效率更高的 __builtin_popcount() 函数，即 123456789template <typename T>  unsigned int __builtin_popcount(T u) {      u = (u & 0x55555555) + ((u >> 1) & 0x55555555);      u = (u & 0x33333333) + ((u >> 2) & 0x33333333);      u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);      u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);      u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);      return u;  } 二分转化为 01...

和 ⩾s\geqslant s⩾s 的最短子区间 12345678910111213141516171819void eachT() { int n = read(), s = read(); vector<ll> pre(n + 1); for (int i = 1; i <= n; ++i) { pre[i] = pre[i - 1] + read(); } int ans = inf; for (int l = 1, r = 1; l <= n; l++) { while (r < n && pre[r] - pre[l - 1] < s) { // 当前不满足 r++; } if (pre[r] - pre[l - 1] >= s) { ans = min(ans, r - l + 1); ...

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; ...