immix's blog

最小割 最小割问题可以简单的这样描述：给定一张带权有向图，除去几条边，使 sss 到 ttt 不连通。求去除的边的权值和最小值。 形式化定义一下：对于图 G=(V,E)G=(V,E)G=(V,E)，将点划分为 SSS 和 T=V−ST=V-ST=V−S 两个集合，其中源点 s∈Ss\in Ss∈S，汇点 t∈Tt\in Tt∈T。我们定义割 (S,T)(S,T)(S,T) 的容量为所有从 SSS 到 TTT 的边的容量之和，即 c(S,T)=∑u∈S,v∈Tc(u,v)c(S,T)=\sum_{u\in S,v\in T}c(u,v)c(S,T)=∑u∈S,v∈T​c(u,v)，最小割问题就是求一个割，使得割的容量 c(S,T)c(S,T)c(S,T) 最小。 最大流最小割定理 最大流最小割定理：f(s,t)max⁡=c(s,t)min⁡f(s,t)_{\max}=c(s,t)_{\min}f(s,t)max​=c(s,t)min​。 即对于一个网络，其最大流与最小割在数值上相等。我们在处理最小割问题时，直接求最大流即可。 求割边数 洛谷P1344 [USACO4.4]追查坏牛奶Pol ...

概念定义 网络：带权有向图 G=(V,E)G=(V,E)G=(V,E)。 容量：边 (u,v)∈E(u,v)\in E(u,v)∈E 的权值，记作 c(u,v)c(u,v)c(u,v)。 源点、汇点： s∈v,t∈v,(s≠t)s\in v , t \in v ,(s\neq t)s∈v,t∈v,(s=t)。 流量：设 f(u,v)f(u,v)f(u,v) 满足 容量限制：对每条边流量不超过容量，即f(u,v)≤c(u,v)f(u,v)\le c(u,v)f(u,v)≤c(u,v) 斜对称性：每条边容量与其相反边容量为0，即f(u,v)=−f(v,u)f(u,v)=-f(v,u)f(u,v)=−f(v,u) 流守恒性：除源点和汇点，流入每个点的流量与流出每个点的容量相同，即 ∀x∈V−{s,t},∑(u,v)∈Ef(u,x)=∑(u,v)∈Ef(x,v)\forall x \in V-\{s,t\},\sum_{(u,v)\in E}f(u,x)=\sum_{(u,v)\in E}f(x,v) ∀x∈V−{s,t},(u,v)∈E∑​f(u,x)=(u,v ...

题目链接-UOJ760 题意 给定一颗有根树，有 nnn 个非叶子节点和 mmm 个叶子节点，000 为根。叶子节点编号为 n,…,n+m−1n,\dots,n+m-1n,…,n+m−1。 叶子节点有一个 {0,1}\{0,1\}{0,1} 中的权值。 对于非叶子节点，权值由如下步骤确定： 对于节点 uuu，设其儿子节点数量为 cuc_ucu​，则任取该节点参数 lu∈[1,cu]l_u\in[1,c_u]lu​∈[1,cu​]。 若 uuu 的儿子节点权值为 111 的个数大于 lul_ulu​ ，则其权值为 111，否则为 000。 现在有 qqq 次修改，每次给定区间 [l,r][l,r][l,r]，反转编号在 [l,r][l,r][l,r] 中的叶子节点的权值（异或 111）。 求出有多少种确定每个非叶子节点参数方式，使根节点的权值为 111。答案对 109+202210^9+2022109+2022 取模。 分析 考虑非叶子节点 uuu，设有 xxx 个儿子权值为 111，yyy 个儿子权值为 000。那么，参数 lul_ulu​ 在 [1,x][1,x][1,x] 范围 ...

前文我们讲了树状数组与线段树基本的实现，本文我们讲线段树的一些优化。 动态开点线段树 我们知道，如果使用二叉树实现，需要给线段树开大小为 4n4n4n 的数组。为了节省空间，我们可以不一次性建好树，而是在最初只建立一个根结点代表整个区间。当我们需要访问某个子区间时，才建立代表这个区间的子结点。我们用ls和rs记录儿子的编号。（结点只有在需要的时候才被创建） 时间复杂度仍为 O(log⁡n)O(\log n)O(logn) 经过 mmm 次操作后，节点的数量规模为 O(mlog⁡n)O(m\log n)O(mlogn)，并且最多也只会创建 2n−12n-12n−1 个节点，没有浪费。 区间修改 12345678910111213void modify(int& o,int l,int r){ if(!o)o=++cnt; if(ql<=l&&r<=qr){ t[o] += qk*(r-l+1); add[o] += qk; return; } pushdow ...

树状数组 一种简单的数据结构。可以做到 O(log⁡n)O(\log n)O(logn) 单点修改，O(log⁡n)O(\log n)O(logn) 区间查询。 维护差分数组可做到 O(log⁡n)O(\log n)O(logn) 区间修改，O(log⁡n)O(\log n)O(logn) 单点查询。 每个元素管理的区间为[i-lowbit(i)+1,i]，lowbit为二进制数的最低位1以及之后的0所组成的数。 123int lowbit(int x){ return x&(-x);} 在补码规则下，x的相反数的二进制表示为~x+1，对x取反后+1，把末尾的0（取反为了1）全部进位到了最低位1的位置，进行位与后得到的便是最低位。 洛谷P3374 【模板】树状数组 1 1234567891011121314151617181920212223242526272829303132333435363738394041#include<bits/stdc++.h>using namespace std;#define ll long longco ...

矩阵 本质是一个二维数表 A=[a1,1a1,2…a1,na2,1a2,2…a1,n⋮⋮⋱⋮am,1am,2…am,n]\mathbf A=\begin{bmatrix} a_{1,1} & a_{1,2} & \dots & a_{1,n} \\ a_{2,1} & a_{2,2} & \dots & a_{1,n} \\ \vdots &\vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \dots & a_{m,n} \\ \end{bmatrix} A=​a1,1​a2,1​⋮am,1​​a1,2​a2,2​⋮am,2​​……⋱…​a1,n​a1,n​⋮am,n​​​ 矩阵乘法 A\mathbf AA 为 m×nm \times nm×n 的矩阵，B\mathbf BB 为 n×pn \times pn×p 的矩阵，C=A×B\mathbf C = \mathbf A \times \mathbf BC=A×B，C\mathbf ...