小明の雜貨鋪

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

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]; }}//...

效率更高的 __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...

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

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

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

和 ⩾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); ...

Strings 子序列 将若干元素提取出来并不改变相对位置形成的序列，不一定连续。 子串 连续的子序列。 后缀 （Suffix）从某位置到整个串末尾结束的子串。 前缀 （Prefix）从串首开始到某位置结束的子串。 字典序 以第 iii 个字符作为第 iii 关键字进行大小比较，空字符小于字符集内任何字符。

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

用于解决多阶段的优化问题。在总体最优策略无法给出的情况下，每一步的选择都是求局部最优解：当求目标函数值最大时，选择当前最大值；当求目标函数值最小时，选择当前最小值。 CF1930D. Sum over all Substrings 题意 对于一个长度为 LLL 的 01 串 ppp，定义一个长度为 LLL 的 01 串 qqq 关于 ppp 是好的，当且仅当 ∀i∈[1,n]\forall i\in[1,n]∀i∈[1,n] 满足：∃1≤l≤i≤r≤L\exists1\leq l\leq i\leq r\leq L∃1≤l≤i≤r≤L，满足 pip_ipi​ 为 q[l,r]q[l,r]q[l,r] 的区间众数。定义 g(p)g(p)g(p) 为所有关于 ppp 是好的串 qqq 中 111 的个数的最小值。 给定一个长度为 nnn 的 010101 串 sss，求 sss 所有子串的 ggg 的和。 思路 贪心地，每个 pi=1p_{i}=1pi​=1 只需要在左中右三个位置之一选择一个填 111。 从前向后遍历，如果 pi=1p_{i}=1pi​=1，可以填...