网络流/二分图相关笔记(应用篇)

请配合 : [网络流/二分图相关笔记(**干货篇**)](https://www.luogu.com.cn/blog/command-block/wang-lao-liu-er-fen-tu-xiang-guan-bi-ji-gan-huo-pian-post) 食用,否则可能无法理解某些内容。 # 1.网络最大流题目泛做 可能会用 $(u,v,f)$ 表示一条从 $u$ 到 $v$ 的,容量为 $f$ 的边。 ## 最大流建模 把流当成移动,路径,选择等等之类。 - [P2472 [SCOI2007]蜥蜴](https://www.luogu.com.cn/problem/P2472) **题意** : 一个矩阵中有若干个石柱,每个石柱都有自己的耐久度。 现在有一些蜥蜴站在部分石柱上,蜥蜴可以跳到欧几里得距离不超过 $d$ 的地方。 蜥蜴每次起跳,脚下的石柱都会失去一点耐久,耐久为$0$则石柱损毁,不能落脚。 问最多能有多少条蜥蜴能够跳出边界。 把蜥蜴的移动当成流,耐久当成容量。 每个石柱需要限流,拆成出入点,之间连上限制。 蜥蜴一开始待在入点。从原点向有蜥蜴的入点连边,容量为$1$。 根据跳跃条件,从出点向其他石柱的入点连边,容量为$\text{INF}$. 能跳出边界的地方,出点向汇点相连,容量为$\text{INF}$. [评测记录](https://www.luogu.com.cn/record/33686828) - [P2766 最长不下降子序列问题](https://www.luogu.com.cn/problem/P2766) 先用朴素`DP`求出 $s$。 然后查看 $f[i]\rightarrow f[j]$ 是否是最优转移,如果是,连上一条边。这样能够保证我们的一条流对应一个最长不降子序列。 每个位置拆点限制流量为 $1$ 。第三问就把 $1,n$ 的限制改改。 然后将 $f[i]=1$ 的位置入点接源, $f[i]=s$ 的位置出点接汇,求最大流即可。 [评测记录(久远)](https://www.luogu.com.cn/record/15529148) - [P2754 [CTSC1999]家园 / 星际转移问题](https://www.luogu.com.cn/problem/P2754) 发现在时间不同时,能走的转移是不同的,考虑按照时间分层。 如果在对应时间有一辆飞船从 $u$ 到 $v$ ,则把该层的 $u$ 连向下一层的 $v$ 。 可以证明,若有解,每经过 $n$ 个单位时间至少运送一个人,这样时间的上界是 $n(k+1)$。 我们可以枚举时间,每次新增一层然后增广,如果超过 $n(k+1)$ 层还没有流完,则无解。 [评测记录](https://www.luogu.com.cn/record/33959830) - [P3163 [CQOI2014]危桥](https://www.luogu.com.cn/problem/P3163) 首先,往返可以看做走双倍次数。 我们按照桥的容量建边,然后分别限制两个源汇的流量,这些都是经典操作。 现在跑最大流,出现了两个问题: - ①可能有些流从 $a_1$ 出发却到达了 $b_2$ ,或者从 $b_1$ 出发到达了 $a_2$。 - ②我们只能限制有向边的流量,可能某些危桥从两个方向都经过 $2$ 次,共 $4$ 次。 难以通过精妙的建模规避掉这些问题。奇妙的是,直接将 $b_1,b_2$ 交换,再次判定即可得到正确答案。 - ①先在 $a_1,b_1\rightarrow a_2,b_2$ 跑一次最大流,可能得到如下情况。(注意是无向图,流可以双向流动) $\begin{cases}a_1\leftrightarrow a_2=a_n-x &b_1\leftrightarrow b_2=b_n-x\\a_1\leftrightarrow b_2=x &b_1\leftrightarrow a_2=x\end{cases}$ 交换 $b_1,b_2$ 后,再跑一次,可能得到如下情况。 $\begin{cases}a_1\leftrightarrow a_2=a_n-y &b_2\leftrightarrow b_1=b_n-y\\a_1\leftrightarrow b_1=y &b_2\leftrightarrow a_2=y\end{cases}$ 不妨设 $x\leq y$ ,能够发现,如果让 $a_1\xleftrightarrow{x} b_2\xleftrightarrow{y} a_2\quad b_1\xleftrightarrow{x} a_2\xleftrightarrow{y} b_2$ 如此衔接,就能构造出符合题意的方案。 若两次最大流任意一次不满,则肯定无解,这是充要条件。 - ②容易发现,同一个源流出的流量不可能从两个方向同时经过一座桥。 危桥从两个方向都被经过,只有可能是 $a_1\rightarrow a_2,\ b_1\rightarrow b_2$ 的两种流都经过。 那么交换 $b_1,b_2$ 后,一种流被反向了,现在是同向,则会一并受到限制。 [评测记录](https://www.luogu.com.cn/record/33920087) - [P5029 T'ill It's Over](https://www.luogu.com.cn/problem/P5029) 容易发现,每节蜈蚣的最优决策都是相同的,我们直接把 $n$ 当做流量即可。 对于每种光明程度,分别建立一个点,源点连 $1$ ,汇点连 $k$。我们的目标是让尽量多的流量来到 $k$。 能够发现,所有的操作都是从一个区间连向另外一个区间,使用一上一下两颗线段树加虚点优化建边即可。 点数是 $O(k+m)$ ,边数是 $O(m\log k)$ ,由于数据随机, `Dinic` 求最大流就已经足够快了。 [评测记录](https://www.luogu.com.cn/record/34072887) ## 匹配问题 这类问题把源当做物品,把汇当做盒子,流的意义是匹配(决策)。 - [P3386 【模板】二分图匹配](https://www.luogu.org/problem/P3386) 二分图的定义见第二节。 我们把左部点设为源,右部点设为汇。每个点只能连一次,所以源汇的容量都是$1$. 把多个点变成源并限制流量 : 从大源给每个小源分别连一条钦定流量的边。 连边可以变成左部点到右部点的一条有向边。 容易理解这些流和匹配是等价的。 有一个结论是`Dinik`跑经典二分图匹配的复杂度是$(n\sqrt{m})$的。 [评测记录](https://www.luogu.com.cn/record/32599579) - [P2055 [ZJOI2009]假期的宿舍](https://www.luogu.com.cn/problem/P2055) 把在学校的人匹配到床上,如果最大匹配$=$总人数,就有解。 具体方法:建立二分图,左边是人,右边是床,每个人向能用的床连边。 [评测记录(久远)](https://www.luogu.com.cn/record/18620093) - [P2763 试题库问题](https://www.luogu.com.cn/problem/P2763) **题意** : 你有$m$个干员,每种干员会做的工作已知。一个干员不能同时做两份工。 $n$ 种工作各自都有需要的人数,问如何分配能满足人手需要。 右侧带容量的二分图匹配。[评测记录(久远)](https://www.luogu.com.cn/record/14862935) - [P3254 圆桌问题](https://www.luogu.com.cn/problem/P3254) 能发现等价于两侧都带容量的二分图匹配。[评测记录(久远)](https://www.luogu.com.cn/record/14992193) - [P4251 [SCOI2015]小凸玩矩阵](https://www.luogu.com.cn/problem/P4251) 考虑二分答案 $lim$ ,这样大于 $lim$ 的位置才被我们考虑。 现在的问题是能否找出 $k$ 个位置满足每行每列都不矛盾。 这可以看做一个二分图匹配问题,行和列分别为左右部点,若某行某列能放置则连边,这样就能满足“一行只对应一列”的条件了。 [评测记录](https://www.luogu.com.cn/record/33688163) - [P2402 奶牛隐藏](https://www.luogu.com.cn/problem/P2402) 先跑`Folyd`。然后二分时间$lim$,这时只有距离$\leq lim$的两个点能够互相通达。 我们要把牛分到牛棚里面去,直接二分图匹配即可。 [评测记录(久远)](https://www.luogu.com.cn/record/22110109) - [CF852D Exploration plan](https://www.luogu.com.cn/problem/CF852D) 仍然考虑二分时间,判定条件变成了最大匹配$\geq m$。[评测记录](https://www.luogu.com.cn/record/33920299) - [CF546E Soldier and Traveling](https://www.luogu.com.cn/problem/CF546E) 每个点上的士兵只能留在自己,或者向相邻的点移动。考虑拆成出入点变为二分图。 从源点连向入点,容量为初始时的人数。从出点连向汇,容量为结束是的人数。 然后对于每条边,从对应入点连向对应出点,边权为 $\inf$。每个点的出入点之间也连 $\inf$ 表示停留。 求最大流。如果初始和结束的总人数不同,或者不满流,则为无解。否则查看反向边的流量输出构造。 [评测记录](https://www.luogu.com.cn/record/33950322) - [CF628F Bear and Fair Set](https://www.luogu.com.cn/problem/CF628F) 差分一下能够发现,这些限制本质上是把 $[1,b]$ 分成了若干段,然后分别限制数的个数。 对于每一段,限制总流量为数的个数。我们分别计算模 $5$ 余 $0...4$ 的数的个数,向对应的 $5$ 个收集节点连边。 如果最大流是 $n$ 则说明有解,否则无解。 [评测记录](https://www.luogu.com.cn/record/33919530) - [P3425 [POI2005]KOS-Dicing](https://www.luogu.com.cn/problem/P3425) 考虑二分或者枚举,问题转化成判定所有人都赢不超过 $lim$ 次的情况下存不存在合法方案。 给每场比赛新建一个点,从源连一条边,限制流量为 $1$,表示只能有一方胜出。然后连向比赛双方。 每个人连向汇点,流量限制为 $lim$ ,若满流则表示有解。 构造方案可以查看比赛的流给了哪一方。 [评测记录](https://www.luogu.com.cn/record/34073267) - [P1231 教辅的组成](https://www.luogu.com.cn/problem/P1231) **题意** : 这是一个三分图。第一层和第二层之间有若干对应关系,第一层和第三层之间也有若干对应关系。同层之间无关系。 如果找出三元组 $(x,y,z)$ 使得其分别属于一二三层,而且 $x$ 与 $y,z$ 都有对应关系,则称为好的。 如果每个点只能用一次,求最多能组成的好的三元组的个数。 初看起来像三分图匹配,但是由于二三层之间无关系,还是能够网络流解决。 把第二层连汇,第三层连源,权值为$1$。中间放第一层,对应关系就是中间的边。 容易发现一条流就对应一个好的三元组。 [评测记录(久远)](https://www.luogu.com.cn/record/14995726) - [P2825 [HEOI2016/TJOI2016]游戏](https://www.luogu.com.cn/problem/P2825) 先考虑没有硬石头的情况。相当于不能在同一行或同一列放置两个炸弹。 类似`P4251`,可以看做一个二分图匹配问题。 若考虑硬石头,可以视作把完整的行/列分成了若干互不影响的段,我们按段的编号建立二分图即可。 [评测记录](https://www.luogu.com.cn/record/33892660) - [P6517 [CEOI2010 day1] alliances](https://www.luogu.com.cn/problem/P6517) 这是个方格图,先黑白染色变成二分图。若没有人类不杠的限制,直接跑二分图多重匹配即可。 能够发现,若不杠又需要两个邻居,一定是一横一竖。我们只需要把人类拆成两个点,一个接一个横,另一个接一个竖即可。 查看匹配情况输出方案。 [评测记录](https://www.luogu.com.cn/record/34080906) - [P3153 [CQOI2009]跳舞](https://www.luogu.com.cn/problem/P3153) 先考虑 $K=0$ ,尝试二分答案。 建立二分图,左侧是男生,流量为 $C$ ,向喜欢的女生连容量为 $1$ 的边,女生向源连容量为 $C$ 的边。 然后跑匹配,如果满流说明答案可以达到 $C$。 接下来考虑 $K$ ,我们额外建立一个点专门用于和不喜欢的人匹配。 男生拆为三个点 : $B,b1,b2$ ( $b1$是喜欢,$b2$是不喜欢 ) 连接 $s\xrightarrow{C} B\ $ 以限制总流量。 连接 $s\xrightarrow{K} b2,\quad s\xrightarrow{C} b2\ $ ,表示最多可以和$K$个不喜欢的人跳舞,喜欢的人随意。 对于女生建图方法类似。 然后在 $(b1,g1),(b2,g2)$ 之间按照意义连边即可。 [评测记录](https://www.luogu.com.cn/record/33875999) - [P3324 [SDOI2015]星际战争](https://www.luogu.com.cn/problem/P3324) 时间这种自带$\max$性质的东西,一般需要二分转化。 二分之后,每个激光武器就相当于针对每个机器人拥有了一定量的“输出值”可以随意分配。 具体地说,每个激光武器的初始容量为 $B[i]*t$ ,向能攻击的机器人连边,机器人到汇的容量是 $A[i]$。 如果最大流满流则说明可以在 $t$ 时间内完成。由于是实数,可能需要扩大 $10^5$ 倍再使用`long long`。 [评测记录](https://www.luogu.com.cn/record/33919889) - [P5038 [SCOI2012]奇怪的游戏](https://www.luogu.com.cn/problem/P5038) 这是个方格图,首先考虑黑黑白染色。每次我们只能对一个黑色的格子和一个白色的格子同时$+1$。 设白色的位置有 $w$ 个,权值和为 $W$ ,类似地有 $b,B$ ,最后全都变成 $c$。 那么需要的操作次数是 $w*c-W=b*c-B$ 听过简单的变形得到 $c=\dfrac{W-B}{w-b}\ (w≠b)$ 若 $w≠b$ 可以直接解出 $c$ 。然而不一定存在合法方案,判断方法同下。 若 $w=b$ ,则 $n,m$ 中必有一个偶数。若全变为 $c$ 可行,由于可以$1\times 2$骨牌密铺,所以可以令整个图都$+1$,则 $c+1$也可行。 满足单调性,可以二分,现在我们的任务就是判断某个 $c$ 是否可行。 我们可以计算出每个点需要加多少次,不难发现两个位置都加一的规则就是二分图带容量匹配。 [评测记录(久远)](https://www.luogu.com.cn/record/14082470) - [P2570 [ZJOI2010]贪吃的老鼠](https://www.luogu.com.cn/problem/P2570) 神仙题.jpg 同样先乘以 $10^5$ 变成整数问题,然后将每块奶酪的存在时间区间离散化。 这样我们就得到 $O(n)$ 个时间段,每段内奶酪的存在情况都是确定的。 我们按照时间段分层,每层中老鼠能够吃的奶酪就是确定的,每只老鼠能够吃多少奶酪也是确定的。 然而现在还有吃奶酪一对一的要求,这里的流量参差不齐,无法像经典二分图匹配那样自然做到一对一。 设某块奶酪在某一段时间 ( 设长度为 $lim$ ) 内被第$i$只老鼠啃了 $t_i$ 单位时间。 注意到时间区间不交就等价于要求 $\sum\limits_{i=1}^nt_i\leq lim$。 这是对所有老鼠共同的限制,如果让每只老鼠分别占用一个点,就不好控制。 先列个式子,这一段内被吃掉的总体积为: $$\sum\limits_{i=1}^nt_iv_i=\sum\limits_{i=1}^nt_i\sum\limits_{j=1}^i(v_j-v_{j-1})=\sum\limits_{j=1}^n(v_j-v_{j-1})\sum\limits_{i=j}^nt_i$$ (不妨按照 $v$ 排序) 这可以看作,令新的第 $i$ 只老鼠速度为 $v_i-v_{i-1}$ ,若第 $i$ 只老鼠吃某个奶酪 $t$ 时间,则 $[1,i)$ 内的老鼠也要吃这个奶酪 $t$ 时间。 可以看出,第 $i$ 只老鼠速度变为 $v^*_i=(v_i-v_{i-1})$ ,时间消耗上限变为 $lim^*_i=lim(n-i+1)$ ,而且新的方案的意义不要求时间不交。 注意到 $\sum\limits_{i=1}^nt_i\leq lim$ ,我们可以在每条老鼠到奶酪的边上限制流量为 $lim(v_i-v_{i-1})$。 通过旧意义下的方案,直接根据那个和式就能得到新意义下的方案。 根据一组新意义下的方案,我们能差分得到 $t$ ,安排出一组满足时间不交的旧方案,这样就建立了双射。 直接求最大流即可。[评测记录](https://www.luogu.com.cn/record/33993950) - [P5786 [CQOI2008]传感器网络](https://www.luogu.com.cn/problem/P5786) 考虑把每个点匹配给自己的父亲,建立二分图,左侧为出点,右侧为入点。 考虑二分/枚举,接下来就需要判断负载级别为 $k$ 是否可行。 每个点只能有一个父亲,于是限制左侧容量一律为 $1$。每个点最多有 $k$ 个儿子,于是限制右侧容量一律为 $k$。 注意,控制中心的流量不受限制。如果满流则有解。 接下来考虑字典序,不难想到逐位贪心。先钦定若干匹配,然后在剩下的图中跑匹配,看看是否满流。 逐位枚举,需要 $O(n^2)$ 次匹配(单流增广)。 [评测记录] () - [P4382 [八省联考2018]劈配](https://www.luogu.com.cn/problem/P4382) 我们考虑将选手匹配向导师。 同阶志愿对于某个选手是没有区别的,所以可能存在后面的选手让前面的选手反悔的情况。 对于每个选手,逐次检查每阶志愿中是否有可能空位,若有,则连向该阶志愿的所有导师并增广。这会留下反向边,自然处理了反悔操作。 现在问题在于如何判断某个导师是否可能有空位。等价于问某个导师的点到汇点是否有增广路,从汇点**反向**搜索即可(注意,图上有环,不能瞎搜)。 这样需要 $O(n)$ 次残量网络上的(单流)增广和`BFS`,复杂度上界是 $O(n^2C)$ 的。 接下来是第二问,不难发现某个前缀所造成的导师“填满”状态是固定的。 二分一下新的排名,然后查看是否能满足要求即可。这部分复杂度是 $O(n^2\log n)$ [评测记录](https://www.luogu.com.cn/record/33995336) - [CF793G Oleg and chess](https://www.luogu.com.cn/problem/CF793G) 这是一个经典的车放置问题,可以二分图匹配解决,但是连$O(n^2)$条边显然无法承受。 考虑优化建边,不难想到主席树+扫描线,这样点数和边数都是 $O(n\log n)$ 的。 另一种更加牛逼的做法是 : 利用题目中黑矩形不交的性质,从每个矩形的**上下边界**向外延伸(遇到障碍就停止),能够将整个图的空位剖分成 $O(n)$ 个矩形。 ```cpp _______________________ ###________________ ###___________## ### #### ## ____###_____####__##___ ____________####_______ ``` 空矩形只有 $O(n)$ 个是因为每个黑矩形只会贡献 $O(1)$ 条边界。 对于每个空矩形,相当于从左部点的一个区间连向右部点的一个区间,我们分别维护两颗线段树即可。 这样边数还是 $O(n\log n)$ ,点数是 $O(n)$ 的 (似乎常数有点大)。 至于这些矩阵怎么划分,反正 $n=10^4$ ,暴力扫描线就是了。[评测记录](https://www.luogu.com.cn/record/33920580) - [CF212A Privatization](https://www.luogu.com.cn/problem/CF212A) 神仙题,找不到题解,看`wxh`神的代码学了一下 /kel。看不懂结论,咕咕。 <https://codeforces.com/contest/212/submission/34274620> ## 棋盘染色 对于一个棋盘,像国际象棋那样染成黑白两色,容易发现这是个二分图。 由于这类题实在太多,这个套路又比较简单,就不单独归类了。 ## 最小割建模 - [P2774 方格取数问题](https://www.luogu.org/problem/P2774) **题意** : 给出一个带权值棋盘,相邻的两个东西不能选,问能选的最大总和。 把网格像国际象棋那样染成黑白两色,容易发现这是个二分图。 这里“不能选”的限制有点类似割,我们考虑最小割。即割的尽量少,保留的尽量多。 相邻的不能选,相当于割断二分图。 我们把中间边设为`INF`,这样不会被割掉。 然后源汇均按权值连边即可。 [评测记录(久远)](https://www.luogu.com.cn/record/8950133) - [P5039 [SHOI2010]最小生成树](https://www.luogu.com.cn/problem/P5039) 根据 `Kruskal` ,其他边$-1$相当于让自己$+1$。 考虑 `Kruskal` 的排序建立过程,把小于 $Lab$ 的边拿出来建图,若$Lab$两端不连通,则可以被选入最小生成树。 使得某条边 $\geq Lab$ 而不被拿来建图的花费是 $Lab-w$ ,以此为边权求最小割即可。 [评测记录](https://www.luogu.com.cn/record/33920705) - [P5934 [清华集训2012]最小生成树](https://www.luogu.com.cn/problem/P5934) 和上一题类似,甚至不需要推结论。 对于最小生成树,取出权值小于关建边的边跑一次最小割。 对于最大生成树,取出权值大于关建边的边跑一次最小割。 [评测记录](https://www.luogu.com.cn/record/34081091) - [P2598 [ZJOI2009]狼和羊的故事](https://www.luogu.com.cn/problem/P2598) 建篱笆就是最小割,源连狼,羊连汇,容量为$\inf$。格子向四连通方向连容量为 $1$ 的边,求最小割。 [评测记录(久远)](https://www.luogu.com.cn/record/11372439) - [P6094 [JSOI2015]圈地](https://www.luogu.com.cn/problem/P6094) 可以让源连南南的房子,强强的房子连汇,容量均为价钱。 每个格子向四连通的方向连对应墙代价的边。 能够发现,一个割就对应着一种合法的方案。(割了房子就代表不卖,割了墙就代表造墙) 将所有可能的收益求和,减去最小割即为答案。 [评测记录](https://www.luogu.com.cn/record/34020374) - [P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查](https://www.luogu.com.cn/problem/P2057) 注意到意见只能有两种,我们可以以 $S,T$ 集来区分。 朋友之间连一条**双向**边,权为 $1$ ,表示如果朋友不在一个集合内需要割断 $1$ 的代价。 对于持有 $\sqrt{}$ 意见的人,从源点连 $1$ , 反之从汇点连 $1$。 求出最小割即为答案。[评测记录(久远)](https://www.luogu.com.cn/record/14997565) - [P3227 [HNOI2013]切糕](https://www.luogu.com.cn/problem/P3227) 鉴于题目很不好懂,特别解释一下题意 : 有一个 $P\times Q\times R$ 的蛋糕,每个点有一个不和谐值 $v[x][y][z]$。 目标是将这个蛋糕切成上下两块。 对于每一竖轴,以$(x,y)$表示。需要在每个竖轴中选择一个断点,设 $(x,y)$ 的断点 $z$ 坐标为 $f(x,y)$。 那么,对于四相邻的竖轴,其 $f$ 值的差不能超过常数 $D$。 目标是使得 $\sum\limits_{x,y}v[x][y][f(x,y)]$ 最小。 我们把蛋糕下表面的点连上源,上表面的点连上汇,这就是一个最小割问题。 如何控制 $f$ 值的差呢? 想办法让差超过 $D$ 的方案连通即可。 我们可以从某个 $z=u$ 的位置,向着四相邻竖轴 $z=u-D$ 的位置连 $\inf$ 边。 这样,如果两个相邻轴的 $f$ 函数差大于 $D$ , $f$ 小的割挡不住 $f$ 大的割的一个侧生边,无法构成最小割。 若两个相邻轴的 $f$ 函数差不超过 $D$ ,则无影响。 按照上述方法建图后求最小割即可。 [评测记录](https://www.luogu.com.cn/record/33962123) - [P6054 [RC-02] 开门大吉](https://www.luogu.com.cn/problem/P6054) 不难发现一套题可以整体处理,首先计算出第 $i$ 为选手答第 $j$ 套题的期望收益 $d_{i,j}=\sum\limits_{t=1}^pc_t\prod\limits_{k=1}^tf_{i,j,k}$。 接下来就是一个分配问题,但是还有若干 “第 $i$ 位选手的套题号必须至少比第 $j$ 位大 $k$ ” 的限制。 不难发现和上一题十分相似,我们可以想办法让差超过 $k$ 的方案连通,只需要这样建图 : 点 $(i,j)$ 表示第 $i$人选择第 $j$ 套题,割掉的代价是 $d_{i,j}$ ,我们要让每个选手选一套题,只需要将 $(i,[1,m])$ 串联即可。 接着,对于一个限制 $(i,j,k)$ 我们从 $(j,r)$ 向着 $(i,r+k)$ 连 $\inf$ 边。 若 $r+k>m$ 则割这个位置肯定不合法,直接向汇连 $\inf$ 边。 能够发现,若最终割掉的两个位置是 $(i,x),(j,y)$ ,当 $x<y+k$ ,就拦不住那条 $\inf$ 边,否则可以拦住。 求最小割即可。流量过大则表明无解,注意适时`break;` [评测记录](https://www.luogu.com.cn/record/34085310) - [P5458 [BJOI2016]水晶](https://www.luogu.com.cn/problem/P5458) 这是一张密铺图,虽然不能像方格图那样染成两色,但是能按照 $(x+y+z)\bmod 3$ 染成三色。 观察发现,共振总是恰好包含三种颜色的水晶各一个。要用最小的代价“割断”共振。 可以看做一个三层图,有若干个限制,每个分别选取每一层的一个点组成三元组 $(a,b,c)$ ,要求它们不能同时存在。 一般的情况不太可做,随手建了个模得了 $40'$ 结果调了一年发现是假的 : [Link](https://www.luogu.com.cn/discuss/show/228425) 观察限制的特殊性,发现能量源的地位十分特殊。 将两种共振综合考虑并讨论,能发现等价的约束 : 某个能量源若存在,其周围最多只能有一种颜色的点。 不妨称能量源为红色,另两种为黑白。则从源连向黑点,从白点连向汇,容量为点权。 接下来,对于一个红点,拆成出入点,中间连边,容量为点权。对于相邻的黑点,连边到入点,对于相邻的白点,从出点连向它们,边权均为 $\inf$。 不难发现,该图的割的条件和转化后的约束等价。 接下来就是最小割了。一些细节 : - 点的位置可以用 $(x-z,y-z)$ 更好地描述,然后用`std::map`检索。 - 由于 $10\%$ 的存在,需要把容量整体乘以 $10$ 变为整数。 [评测记录](https://www.luogu.com.cn/record/34024153) - [P3756 [CQOI2017]老C的方块](https://www.luogu.com.cn/problem/P3756) 仍然是一道奇怪的题目。 发现四种形状都恰好包含一条蓝色竖线和四个格子,那么不妨把方格图染成四色,使得每个形状恰好含有四种颜色各一个。 经过一阵手玩之后,染成了这样:  有了上一题的教训,我们不拆分,综合考虑这些限制,发现**等价于**要求下列子图中,四种颜色不能同时存在。  那么我们按照右侧的方法建边,就能限制至少割掉一种颜色。 接下来就是大量染色和连边的细节,就不赘述了。 最后求最小割,由于图近似二分图, $10^5$ 也能过。[评测记录] () - [P1791 [国家集训队]人员雇佣](https://www.luogu.com.cn/problem/P1791) 若一个人在 $S$ 集中则表示选择,在 $T$ 集中则表示不选。 先不考虑竞争。从源点给每个人连边 $\sum\limits_{i=1}^n E_{u,i}$ ,连到汇点的边是 $A_u$。表示要么舍弃收益,要么付出代价。 考虑 $E_{i,j}$ 贡献的限制,$i,j$ 之间连双向边 $E_{i,j}$ 即可,这样若一个在 $S$,一个在 $T$,就必须割掉,否则不用割。 接着考虑竞争,这会令 $S$ 集和 $T$ 集之间关于双人的割代价翻倍,也就是 $i,j$ 之间连双向边 $2*E_{i,j}$。 接着就是求总收益减去最小割( 需要`long long` ),由于边非常多,可能需要卡常。 [评测记录](https://www.luogu.com.cn/record/34024891) - [P1361 小M的作物](https://www.luogu.com.cn/problem/P1361) **题意** : 把若干个物品分配到$A,B$两个盒子里面。每个物品分到不同的盒子有不同的收益。 同时,钦定若干个物品集合一并丢到某个盒子里面的额外收益。 用最大流的思路并不容易建模。注意到这里只有两个盒子,选某个盒子可以看做割另一个盒子。 首先建立一个不考虑集合的图。可以把每个点**串联**$A,B$的权值边,这样只会割掉其中一个。 不难想到$A$做源,$B$做汇,中间是物品,边为对应权值。 现在考虑集合,对于某个集合,如果其中某个点的$A$边被割掉,那么其集合$A$边也必然被割掉。 我们可以考虑把集合$A$边和其内的物品$A$边**并联**,这样一旦要割必然一起割掉。 这样,我们对每个集合建立$A$虚点,和源相连,边权为集合权值。 然后连边到对应的物品上,边权为`INF`防止被割。 如果要割掉任意一个物品边,都必须要割掉所对应的所有集合边,否则白割。 整张图是对称的,对 $B$ 集合的连边类似。 由于图很稠密,写`vector`会快一点(`2`倍速左右) [评测记录](https://www.luogu.com.cn/record/32601208) - [P4313 文理分科](https://www.luogu.com.cn/problem/P4313) 棋盘和四连通是吓唬人的,根本不需要黑白染色,其实就是 `P1361`。[评测记录](https://www.luogu.com.cn/record/33876727) - [P1646 [国家集训队]happiness](https://www.luogu.com.cn/problem/P1646) 棋盘和四连通又是吓唬人的,其实就是 `P1361`。[评测记录](https://www.luogu.com.cn/record/33877003) - [CF311E Biologist](https://www.luogu.com.cn/problem/CF311E) 其实就是 `P1361`,只不过多了个倒贴钱。[评测记录](https://www.luogu.com.cn/record/33877419) - [P1935 [国家集训队]圈地计划](https://www.luogu.com.cn/problem/P1935) 这是个四连通网格图,先黑白染色变成二分图。 不相同才有奖很不爽,直接交换右部点的 $A,B$ ,变成相同有奖。 然后就是`P1646`了。[评测记录](https://www.luogu.com.cn/record/34025179) - [P3308 [SDOI2014]LIS](https://www.luogu.com.cn/problem/P3308) 模仿`P2766`,首先还是`DP`求出`LIS`。 画出最优转移的`DAG`,我们的目标就是把这个`DAG`割了。 每个位置拆点,点权为 $B[i]$ ,最优转移边权为 $\inf$ ,求最小割, 能得到第一问的答案。 考虑构造一组字典序最小的最小割,一个简单的想法是逐位贪心,但是(就算使用二分)仍然需要求 $O(n\log n)$ 次最小割,效率低下。 回忆上文“最小割的必须边和可行边”。 我们可以先安排一个 $c$ 尽量小的可行边,然后排除掉等价的其他可行边。 一种暴力的想法是,删掉这条边,重新跑一次最大流。这需要 $O(n)$ 次最大流,仍然很低效。 我们考虑在原网络信息的基础上进行调整。 接下来引入一种重要的操作 : **退流**。 观察删去某条边$(u\rightarrow v)$之后的网络,该边的两个端点的流量就不守恒了。 考虑调整,不难发现从 $u\rightarrow S$ 跑一次最大流,从 $T\rightarrow v$ 跑一次最大流,把这条边的流量退回去。 这样仍然需要 $O(n)$ 次退流,但是肯定比 $O(n)$ 次完整的最大流快。 能够发现退流往往只会涉及部分网络,最好使用不完全`BFS`优化。 前面提到,可以缩`SCC`求可行边,但是这题的图在不断变化,只好直接暴力搜索,查看是否有增广路。 搜索的复杂度上界是 $O(nm)=O(n^3)$ 的,似乎不太行。由于问题的特殊性随便写一点剪枝就很快了。 [评测记录](https://www.luogu.com.cn/record/33921873) - [CF724E Goods transportation](https://www.luogu.com.cn/problem/CF724E) 首先有一个显然的最大流解法 : $S\xrightarrow{\small p_i}i\xrightarrow{\small s_i}T$,以及 $i\xrightarrow{\small c}j\ (i<j)$。 然而数据范围很大,就算使用区间数据结构优化建边也过不去。 注意到图很特殊,我们考虑使用`DP`求解最小割,就能得到最大流。 设 $dp[i][j]$ 为前 $i$ 个点 $j$ 个在 $S$ 集的最小割。在第 $i$ 个点分类讨论 : - 若在 $S$ 集中,则需要割断与 $T$ 集之间的边,以及本身到 $T$ 的边。 - 若在 $T$ 集中,则只需要隔断与 $S$ 集之间的边。 转移方程 : $dp[i][j]=\min\big(dp[i-1][j-1]+s_i+c(i-j),dp[i-1][j]+p_i\big)$ 最后 $\min\limits_{i=0}^n dp[n][i]$ 即为答案。 暴力求解(需要滚动数组),复杂度为 $O(n^2)$ ,已经可以通过。 设最终方案为集合 $S,T$ ,则代价为 $\sum\limits_{u\in S}s_u+\sum\limits_{v\in T} p_v+c\sum\limits_{u\in S,v\in T}[u<v]$ 不妨令初始状态为所有点都在 $T$ 集合,此时的割代价为 $\sum\limits_{i=1}^n p_i$。 若将 $i$ 从 $T$ 集中拿出来加入 $S$ 集,割代价的变化量是 : $$c\big((n-i)-|S|\big)+s_i-p_i$$ 要割的边数 $(n-i)-|S|$ 怎么得来呢? 若都是 $T$ 集, $i$ 要和后面的 $n-i$ 个位置断边。 现在已经有 $|S|$ 个位置不是 $T$ 集了,若在 $i$ 前面,则 $i$ 把他们的右端点占了,若在 $i$ 后面,则把 $i$ 的左端点占了,总会减少 $|S|$ 条边。 不难发现,关于 $c$ 的贡献和 $i$ 是谁无关,也就是说和 $s_i,p_i$ 无关,只和 $i$ 第几个加入有关。 我们把 $i$ 的权值设为 $c(n-i)+s_i-p_i$ ,若第 $k$ 个将其加入,则 额外减去 $c(k-1)$。 加入的过程中,每种状态都是一个合法的割。 考虑如何让这个过程中产生的割代价“最低点”最小,显然应该先加入权值尽量小的点。 按照权值排序贪心即可,复杂度 $O(n\log n)$。 [评测记录](https://www.luogu.com.cn/record/34026671) ## 最大闭合子图建模 - [P3410 拍照](https://www.luogu.com.cn/problem/P3410) **题意** : 有$n$个元素,要求选择若干个组成集合$S$,选择每个元素都有代价。 给出若干个悬赏$T$,如果$T\subseteq S$则获得该悬赏的奖励,问最大净收益。 经典问题。元素必须集齐可以转化成闭合子图条件。 每个悬赏点权为奖励,出边连向所需的所有元素。这样,由于图闭合,想获得奖励,所有这些元素都必选。 元素的点权为(负)自己的代价。跑最大闭合子图模板即可。 [评测记录](https://www.luogu.com.cn/record/33671680) 希望构造方案请见 [P2762 太空飞行计划问题](https://www.luogu.com.cn/problem/P2762) - [P2805 [NOI2009]植物大战僵尸](https://www.luogu.com.cn/problem/P2805) 发现不会做这道题是写作本文的动力之一。 **题意** : 一个网格图上,有若干个法阵,每个都有其防御位置集合。 我们可以从地图右侧发射光球,向左飞行。如果光球途径某个(未摧毁)法阵的防御范围,则会被吸收而不能起到攻击作用。 对于一个法阵,如果其能源参数为负数,则表示摧毁这个法阵需要付出能源,否则表示能收益能源。 问在这次攻击行动中,能获得多少能源的净收益? 而要想摧毁一个法阵,必须要把防御它的其他法阵都干掉,则对应“出边必选”的闭合条件。 由于光球只能向左飞行,摧毁一个法阵需要摧毁之前的所有法阵,可以认为每个法阵会保护身后的一个。 我们将每个法阵向防御它的所有法阵连边,然后求最大闭合子图即可。 问题在于可能有一些法阵互相保护,这些法阵就相当于无敌了(和经典的最大权闭合子图不同),被它们保护的其他法阵也无敌了。 可以在反图上拓扑排序取出没有无敌效果的点。 [评测记录](https://www.luogu.com.cn/record/33878259) - [AT3672 [ARC085C] MUL](https://www.luogu.com.cn/problem/AT3672) 能够发现, 若打碎第 $k$ 个水晶,则必须打碎编号为 $k$ 的倍数的水晶。(这类约束很可能是个`DAG`,排个序看看就得到了) 然后我们可以从 $k$ 向着 $2k,3k,4k...$ 连边( 共 $O(n\log n)$ 条 ),这样打碎的水晶就是闭合子图,求最小权闭合子图即可。 注意需要开`long long`。 [评测记录](https://atcoder.jp/contests/arc085/submissions/13738923) - [P4174 [NOI2006]最大获利](https://www.luogu.com.cn/problem/P4174) 某个用户能贡献当且仅当其使用的两个基站都建造,最大闭合子图模板题。[评测记录](https://www.luogu.com.cn/record/33878336) - [CF1082G Petya and Graph](https://www.luogu.com.cn/problem/CF1082G) 选某条边一定要选两个端点,变成 `P4174`。[评测记录](https://www.luogu.com.cn/record/33878372) - [P3973 [TJOI2015]线性代数](https://www.luogu.com.cn/problem/P3973) 首先把式子化一化 : (不熟悉线性代数是不是就跪了啊……) $D=(A\times B-C)*A^{\rm T}$ $=\sum\limits_{j=1}^n(\sum\limits_{i=1}^nA[i]*B[i][j]-C[j])*A[j]$ $=\sum\limits_{i=1}^nA[i]*\sum\limits_{j=1}^nA[j]*B[i][j]-\sum\limits_{j=1}^nC[j]*A[j]$ 能够发现,如果选择 $A[i]$ ,则会带来 $C[i]$ 的损失,如果 $A[i],A[j]$ 都选,则有 $B[i][j]$ 的收益。 搞了半天原来还是同一个题,直接最大闭合子图带……走? 点似乎有 $O(n^2)$ 个啊,不太行。(好像由于数据水也能过,但是太丑了) 考虑到该类问题的特殊性($A$只有两种取值),直接使用更加接近本质的**最小割**来分析。 若 $u∈S$ ,表示 $A[u]=1$ ,反之 $u∈T$ 表示 $A[u]=0$ 。 对于一组$(x,y)$,分类讨论: - $x,y∈S$ 损失 : $C[x]+C[y]$ - $x\in S,y\in T$ 损失 : $B[x][y]+B[y][x]+C[y]$ - $x\in T,y\in S$ 损失 : $B[x][y]+B[y][x]+C[y]$ - $x,y\in T$ 损失 : $B[x][x]+B[y][y]+B[x][y]+B[y][x]$ 在最小割中,如果想要仅用 $O(n)$ 的点数,我们最多只能做到这样连边:  考虑每种情况中割掉的边以及对应的损失,能得到方程组: $$\begin{cases}bx+by=C[x]+C[y]\\bx+v+ay=B[y][y]+B[x][y]+B[y][x]+C[y]\\ax+v+by=B[x][x]+B[x][y]+B[y][x]+C[y]\\ax+ay=B[x][x]+B[y][y]+B[x][y]+B[y][x]\end{cases}$$ 解这个方程组,发现没有产生矛盾。解得: $$\begin{cases}bx=C[x]\\by=C[y]\\ax=B[x][x]+\frac{1}{2}(B[x][y]+B[y][x])\\ay=B[y][y]+\frac{1}{2}(B[x][y]+B[y][x])\\v=\frac{1}{2}(B[x][y]+B[y][x])\end{cases}$$ 上面是两个点的情况,现在考虑多个点的情况。 $v$ 边不会重合,自然正确。而 $a,b$ 边会重合。 根据题意,$C$只用算一次贡献,所以仍然有 $bx=C[x],\ by=C[y]$。 对于 $a$ 边,其包含的$B$贡献是需要累加的,即 $ax=B[x][x]+\dfrac{1}{2}\sum\limits_{i=1,i≠x}^nB[x][i]+B[i][x]\ =\dfrac{1}{2}\sum\limits_{i=1}^nB[x][i]+B[i][x]$ 为了避免小数,把流量扩大一倍,求最小割即可。 [评测记录](https://www.luogu.com.cn/record/33923894) 前面的几个题也都可以如此减少点数到 $O(n)$ 级别 ( 而非 $O(m)$ )。 - [P3749 [六省联考2017]寿司餐厅](https://www.luogu.com.cn/problem/P3749) 首先能够发现,由于可以取多次,每次只取一个区间的限制可以忽略。 观察代价计算方式,每种代号的寿司,只要吃任意一种,都会带来 $mx^2$ 的代价。而除此之外,任意多吃一种,都只需要 $x$ 的代价。 而观察 $d$ 的记忆性规则,能联想到闭合子图。 注意到 $[i,j]=[i,j-1]∩[i+1,j]$ ,我们从 $d[i][j]$ 向 $d[i+1][j],d[i][j-1]$ 连边即可。 ( 分别向每个寿司连边不仅效率低下,由于 $d$ 有负数,正确性也有问题 ) 然后,对于代表单种寿司的 $d[i][i]$ ,将点权减去 $x$ ,并向代表其代号的点(点权为 $-mx^2$)连边。 求最大权闭合子图即可。[评测记录](https://www.luogu.com.cn/record/33924184) - [P3872 [TJOI2010]电影迷](https://www.luogu.com.cn/problem/P3872) 一种扩展的最大闭合子图。原先是要求一定闭合,现在可以花费某种代价删去一条有向边的约束。 仍然考虑类似的建图,正权点连源,负权点连汇,有向边的边权不再是 $\inf$ 而是割掉的代价。 答案仍然是正点权和减去最小割。[评测记录](https://www.luogu.com.cn/record/34081477) - [P4177 [CEOI2008]order](https://www.luogu.com.cn/problem/P4177) 若不存在租用,完成一项工作必须购买对应的所有机器,这就是个经典的最大闭合子图问题。 接着考虑租用,可以类似上一题,将租用视作花费一定代价忽略某条边的闭合限制。 即 : 从每个工作向对应的机器连边,边权为租用费用。然后求解扩展最大闭合子图。 [评测记录](https://www.luogu.com.cn/record/34081612) - [CF103E Buying Sets](https://www.luogu.com.cn/problem/CF103E) 容易发现,题目中给出的特殊性质就是 $\rm Hall$ 定理。 所以我们建立二分图,左侧是集合,右侧是元素,集合向其中的元素连边,一定有完美匹配。 任取一种完美匹配,不妨设集合 $i$ 匹配到了元素 $p_i$。 我们取 $k$ 个集合的匹配元素集合,就能得到这 $k$ 个集合的并集的一个子集。 若子集等于并集,这就是一个合法解,若并集更大则不合法。考虑如何限制,不难想到利用闭合子图。 让集合向着所包含的元素连边(强制选并集),元素沿着完美匹配向着集合连边,求最小权闭合子图即可。 [评测记录](https://www.luogu.com.cn/record/34029124) - [P5295 [北京省选集训2019]图的难题](https://www.luogu.com.cn/problem/P5295) & [B. 【UR #11】元旦老人与丛林](http://uoj.ac/contest/23/problem/168) 首先可以手玩一下,能够发现一个图合法的必要条件 : $V\geq 2E-2$ 这是比较显然的, $V=2E-2$ 时最好也就是黑白两颗树,任意多一条边都会导致形成环。 接着,我们猜想 : 若每个子图都满足 $V\geq 2E-2$ ,则整个图可解。 证明比较神仙,看这里 : <http://jiry-2.blog.uoj.ac/blog/1115> 考虑给边赋权 $1$ ,点赋权 $-2$ ,套用 `CF1082G` ,得到权最大的子图。 若这个权大于 $-2$ ,则无解,否则有解。 但是注意道我们总是可以选择空集,所以总是得不到负数的结果。也就是说我们真正想求的是“最大权**非空**闭合子图”。 可以采用比较暴力的办法,直接枚举必选那个点(容易发现只需要枚举“点”),然后给剩余的部分跑一遍完整的最大权闭合子图。 由于这是二分图,复杂度是 $O(nm\sqrt{n})$ ,在洛谷已经可以通过。[评测记录] () 每次都重新跑十分浪费,注意到删除一个点只是相当于删掉了右部点到汇的一条容量为 $2$ 的边。 我们一开始做一个二分图匹配,每次直接把被删除边的流量退掉即可。 由于流量很少,复杂度是有理有据的 $O(nm)$。[评测记录] () ## DAG(偏序集)建模 - [P2172 [国家集训队]部落战争](https://www.luogu.com.cn/problem/P2172) 观察到只能向下移动,这是个 `DAG` ,然后求解(点不相交)的最小路径覆盖即可。 [评测记录](https://www.luogu.com.cn/record/33898214) - [P5769 [JSOI2016]飞机调度](https://www.luogu.com.cn/problem/P5769) 发现按时间分层点数太多无法承受,注意到任务数量较少,而且都以绝对时间标定,不妨将任务看成状态。 先使用 `Folyd` (注意维修时间)求出两两最短路,然后将每个任务连向完成后(注意必须直飞)还来得及接的其余任务。 按起飞时间排序,我们能发现这是个`DAG`,跑最小路径覆盖即可。 [评测记录](https://www.luogu.com.cn/record/33924584) - [P4589 [TJOI2018]智力竞赛](https://www.luogu.com.cn/problem/P4589) 考虑二分,每次判定能否答完价值低于 $mid$ 的问题。 问题转化成 : 给出一个`DAG`,使用允许相交的 $n+1$ 条链进行覆盖,能否把关键点全部盖住。 搞个传递闭包就转化成可相交链覆盖了。 由于点数较少,也可以直接枚举并加边。[评测记录](https://www.luogu.com.cn/record/34085548) - [CF590E Birthday](https://www.luogu.com.cn/problem/CF590E) 首先能够发现,包含关系是一个偏序集。 建立`AC`自动机,众所周知,`fail`树中,祖先是儿子的子串。 暴力跳`fail`连边复杂度是$O(n*len)$的,不可取。(听说`dfs`遍历`fail`树会爆栈) 一个比较好的方法是,每个点向最近的一个祖先连边,然后传递闭包。 然后就变成了最长反链问题,复杂度为$O(n^3+len)$。[评测记录](https://www.luogu.com.cn/record/33695180) ## 二分图建模 比较平凡的二分图匹配除外。 - [P3355 骑士共存问题](https://www.luogu.com.cn/problem/P3355) 能够发现影响是二分图。(国际象棋中,骑士走一步,落脚点和起点的颜色一定不同) 然后求解二分图最大独立集。 [评测记录](https://www.luogu.com.cn/record/33898559) - [P3033 [USACO11NOV]Cow Steeplechase G](https://www.luogu.com.cn/problem/P3033) 容易发现横线段互不相交,竖线段互不相交,这是个二分图。 选出互不相交的尽量多的线段,等价于二分图最大独立集。 [评测记录](https://www.luogu.com.cn/record/34086032) - [P2423 [HEOI2012]朋友圈](https://www.luogu.com.cn/problem/P2423) 题意就是让我们求解朋友关系的最大团。在一般图中,这是个`NP`问题,我们需要利用本题中图的特殊性质。 观察 $A$ 中的人, 发现朋友关系是和最后一位有关的二分图,这样,我们在 $A$ 中只有可能选择 $0,1,2$ 个人,可以暴力枚举。 观察 $B$ 中的人, 可以发现补图也是个二分图。由于原图的最大团等于补图的最大独立集,求解二分图最大独立集即可。 出题人比较憨逼,给这么大的数据范围,然而造得很水,我们可以随手加几个剪枝用`Dinic`跑过去…… [评测记录](https://www.luogu.com.cn/record/33899280) - [CF976F Minimal k-covering](https://www.luogu.com.cn/problem/CF976F) 发现没见过类似的模型,直接做比较困难。 不妨对答案方案取补,限制就变成了 : 每个点最多被连接 $d_i-k$ 次。 我们求出(带容量的)最大匹配,然后取补就能得到最小的 $\rm k-match$ 集。 对每个 $k$ 重新建图效率低下,能够发现 $k$ 减小 $1$ 之后,相当于图中的某些边容量集体增大 $1$ ,在残量网络上增广即可更快地计算。 [评测记录](https://www.luogu.com.cn/record/33925130) - [CF1198E Rectangle Painting 2](https://www.luogu.com.cn/problem/CF1198E) 注意到代价是$\min$,肯定每次涂一整行或者一整列最优。 现在问题就是,对于每个黑点,要么所在的行被涂黑,要么所在的列被涂黑。 这能够转化成二分图最大点覆盖问题 : 行在左边,列在右边,黑点是中间的边。 但是正方形网格非常大,黑色矩形却很少。 考虑暴力离散化得到 $O(m^2)$ 个矩形,然后就是个带容量的二分图最小点覆盖了(等于最大流)。 [评测记录](https://www.luogu.com.cn/record/33926481) - [CF786E ALT](https://www.luogu.com.cn/problem/CF786E) 将居民和守卫看做二分图,居民对守卫的要求看做边。不难发现这个二分图的最小点覆盖就是答案。 显然 $O(n^2)$ 条边是无法承受的,考虑优化建边,由于这是树,考虑树剖。点数 $O(n)$ ,边数 $O(n\log^2n)$ 。 构造方案需要按照割集查看,不能直接利用二分图的性质了。 [评测记录](https://www.luogu.com.cn/record/22965030) - [P4055 [JSOI2009]游戏](https://www.luogu.com.cn/problem/P4055) 这是个方格图,首先黑白染色变成二分图。 现在就把问题抽象成了一个二分图博弈 : 可以自行选取起点,通过二分图上的边移动,并将该边删去,不能移动者负。 先求出一个最大匹配,假设先手选在某个**非匹配点**开始。 那么,若没有出边,则后手负。若有出边,则后手必定来到匹配点,否则可以增广。 接着,先手可以走匹配边,这样又变成了后手到达非匹配点的局面。 若有出边则后手必定来到匹配点,否则产生交错路,可以增广。 先手总是可以走匹配边,后手必败。 而最大匹配可能有多种,某个点只需要在其中任意一种不是匹配点,先手都有必胜策略。 接着说明其他的点都是先手必败。这些点必然总是匹配点,那么后手操作一次之后就总是变成先手到达非匹配点的局面,先手必败。 所以我们求出所有**可能的非匹配点**,即为答案。 大多数人都是用的匈牙利,所以判断非匹配点在二分图上`dfs`一下偶路径就好了。 网络流也不是不能做,枚举每条满流边,把流量退掉,查看是否存在新的增广路。这可以搜索出 $S,T$ 集之后$O(m)$快速求出。 总复杂度就是 $O(E\sqrt{V})=O(n^3)$ 。 [评测记录](https://www.luogu.com.cn/record/34088635) ## Hall定理 - [P3488 [POI2009]LYZ-Ice Skates](https://www.luogu.com.cn/problem/P3488) 可以二分图匹配做,但是数据范围太大,观察到只需要判定是否有完美匹配,考虑Hall定理。 每次操作会增加 $x$ 个 $t$ 号点,并向着右侧的 $[t,t+d]$ 每个点都连边。 能够发现 : 左侧选择**连续**型号的人,能够使得连向右侧的点集尽量小。 也就是说,我们要求左侧对于任意的 $sum[l,r]\leq k*(r-l+1+d)$ 令左侧的每个点点权减去 $k$ ,则有 $sum[l,r]\leq k*d$ 线段树维护最大子段和查看是否 $\leq k*d$ 即可。 [评测记录](https://www.luogu.com.cn/record/33900258) - [CF981F Round Marriage](https://www.luogu.com.cn/problem/CF981F) 考虑二分,然后转化成了判定二分图是否有完美匹配。 先拆环为链,距离不超过环长的一半,这是合法的。 和上一题中类似,选择连续的 `boy` ,能够使得连向 `girl` 的点集尽量小。 设 $tl[i]$ 为 第 $i$ 个 `boy` 最靠左能匹配到的 `girl` 编号, $tr[i]$ 类似。(可以利用单调性 $O(n)$ 求解) 对区间 $[l,r]$ 的要求可以写作 $tr[r]-tl[l]\geq r-l$ 可变形为 $tr[r]-r\geq tl[l]-l$ 前缀 $\max$ 判定即可,复杂度为 $O(n\log L)$。 [评测记录] () - [#6062. 「2017 山东一轮集训 Day2」Pair](https://loj.ac/problem/6062) 对于 $A$ 的每个长度为 $m$ 的子区间判断是否和 $B$ 有完美匹配。 将 $B$ **降序**排序。能够发现, $A$ 中的一个元素能够匹配的 $B$ 元素一定是一个前缀。 类似地,选择 $A$ 中**升序**排序之后的前缀 ,能够使得连向 $B$ 的点集尽量小。 对两个序列前缀的限制可以等价为 : $B_i$ 至少要被匹配 ${m-i+1}$ 次。 先离散化,每个 $A$ 所新增的匹配次数是一个区间加,依次处理区间,每次移动相当于一次增加和一次删除。 事先将 $B_i$ 置为 $-(m-i+1)$ ,然后线段树维护最小值,看看是否 $\geq 0$ 即可。 [评测记录](https://loj.ac/submission/817461) - [CF1009G Allowed Letters](https://www.luogu.com.cn/problem/CF1009G) 可以按照字典序贪心,但是可能导致后面没东西填,产生后效性。 填写每一位之前,可以先判断一下后面的位能否形成完美匹配,如果能才填写。 具体的讲,每个字母按照数量限制流量,右边连向每个位置,跑二分图带容量匹配看看是否满流即可。 但是这会需要 $O(n\Sigma)$ 次二分图匹配,显然无法承受。考虑到我们只需要判断是否形成完美匹配,可以使用扩展霍尔定理。 又能发现字符串上的一个位置最多只有 $O(2^\Sigma)$ 种限制,可以把限制相同的点直接压起来。 观察填写一个位置可能造成的影响 : 一个右侧点和一个左侧点容量一并减少 $1$。 那么,可以每次填写后 $O(2^\Sigma)$ 暴力枚举左侧的点集,能够发现右侧的邻域就是 : 全集减去补集的子集求和。 暴力维护一下子集求和就可以$O(1)$判定了。总复杂度是$O(n2^{\Sigma})$。 [评测记录](https://www.luogu.com.cn/record/34089632) - [AT2645 [ARC076D] Exhausted?](https://www.luogu.com.cn/problem/AT2645) [[??记录]AT2645 [ARC076D] Exhausted?](https://www.luogu.com.cn/blog/command-block/post-ji-lu-at2645-arc076d-exhausted) - [CFgym102268D Dates](https://codeforces.com/gym/102268/problem/D) 暂咕。 ## 最小割树 - [P3329 [ZJOI2011]最小割](https://www.luogu.com.cn/problem/P3329) 建立最小割树,枚举源点暴力 `dfs` 求每两个点之间的最小割即可。[评测记录](https://www.luogu.com.cn/record/33980109) - [UVA11594 All Pairs Maximum Flow](https://www.luogu.com.cn/problem/UVA11594) 做法同上,注意行末不能有空格。[评测记录](https://www.luogu.com.cn/record/33980568) - [P4123 [CQOI2016]不同的最小割](https://www.luogu.com.cn/problem/P4123) 把最小割树的边权丢进 `std::set` 然后输出 `size()` 即可。[评测记录](https://www.luogu.com.cn/record/33980903) - [P3729 曼哈顿计划EX](https://www.luogu.com.cn/problem/P3729) 安全系数其实就是最小割。一个点集的最小割等于其中任意两点的最小割的 $\min$ ,也就等于最小割树中点集内部的最小边权。 建立最小割树,问题变为 : 选择一个点集,在满足权值和 $\geq k$ 的前提下,点集内部的最小边尽量大。 这可以把最小割树中的边按权值从大到小依次加入,使用并查集维护最大的联通块权值和。离线从小到大回答询问。 [评测记录](https://www.luogu.com.cn/record/33983417) - [CF343E Pumping Stations](https://www.luogu.com.cn/problem/CF343E) 建立最小割树,相当于在树上按一个排列移动,求路径$\min$的和的最大值。(这就开始和最小割无关了) 考虑限制最紧的一条边 : 权值最小的那条边。 我们要尽量少地经过这条边,至少经过一次,也容易构造出这个下界。 然后,我们这条边删去,得到两颗子树,变为子问题。 合并时将两棵子树的排列直接接在一起即可,接口上恰好经过一次权值最小的边。 这部分复杂度$O(n^2)$。 [评测记录](https://www.luogu.com.cn/record/33984578) # 2.费用流题目泛做 可能会用 $(u,v,f,c)$ 表示一条从 $u$ 到 $v$ 的,容量为 $f$ ,费用为 $c$ 的边。 ## 类最短(长)路问题 - [P2153 [SDOI2009]晨跑](https://www.luogu.com.cn/problem/P2153) 注意到点不相交的限制,拆点并限制流量为$1$。原图中的边不限流量,费用为边权。 [评测记录(久远)](https://www.luogu.com.cn/record/14997026) - [P2045 方格取数加强版](https://www.luogu.com.cn/problem/P2045) 没有点不相交的限制,但是每个点只能贡献一次。 把每个点拆成出入点,之间有两条边,一条只能走一次,但是能贡献费用,另一条可以走无穷多次,但是费用为$0$。 原图的边不限流量,无费用。 然后跑最大费用最大流即可。(增广路较长,费用范围大,图稀疏,不使用`zkw`的一例) [评测记录(久远)](https://www.luogu.com.cn/record/14952307) - [P4013 数字梯形问题](https://www.luogu.com.cn/problem/P4013) 拆点,之间的边费用为点权。 - 限制① : 点限制流量为$1$,边限制流量为$1$ - 限制② : 点不限流量,边限制流量为$1$ - 限制③ : 点和边均不限制流量。 [评测记录](https://www.luogu.com.cn/record/33900566) - [P3356 火星探险问题](https://www.luogu.com.cn/problem/P3356) 我们将每个位置拆成出入点,先连上`INF`边,若有石块,额外连一条容量费用均为$1$的边。 容易发现这是个`DAG`,原图的边不限流量。求最大费用最大流即可。 主要难点在于输出方案,通过比对原图和残量网络能够得到每条边被多少辆车子经过。 [评测记录](https://www.luogu.com.cn/record/33927553) - [P4012 深海机器人问题](https://www.luogu.com.cn/problem/P4012) 和上一题差不多,只不过贡献在边上,而且变成了多源多汇。(甚至不需要输出方案) [评测记录](https://www.luogu.com.cn/record/33928095) - [CF818G Four Melodies](https://www.luogu.com.cn/problem/CF818G) 我们考虑让一个流代表一个子序列,那么流只能从左往右,这是个`DAG`。 要长度总和尽量大且不交,非常套路地把每个位置拆点,限制容量为 $1$ 费用为 $1$。 直接按照题目中给出的限制向后连边,可能会产生 $O(n^2)$ 条边,无法承受。 能够发现,对于模 $7$ 的限制,我们,然后使用传递性即可。这需要建立$\inf$边来表示经过但不选取。 对于 $±1$ 的限制,能够发现满足条件的集合模 $7$ 也是同余的,那么只需要连接后面最靠近的点。 求最大费用最大流即可。[评测记录](https://www.luogu.com.cn/record/33928460) - [UVA1486 Transportation](https://www.luogu.com.cn/problem/UVA1486) 考虑差分建边,也就是给每条边的每单位流量单独建边,容量为 $1$ ,费用可以单独控制。 第 $x$ 单位流量的费用为 $a_i\big(x^2-(x-1)^2\big)$。 这样,如果流了代表流量 $1,2,3...k$ 的边,费用就恰好是 $$a_i(k^2-(k-1)^2+(k-1)^2-(k-2)^2+...+2^2-1^2+1^2-0^2)=a_ik^2$$ 由于平方的凸性,最小费用流一定会先走代表流量低的边,这就保证了合法性。 由于容量很小,直接建就好了。接着就是最小费用最大流的模板了。 [评测记录](https://www.luogu.com.cn/record/34092206) - [CF1187G Gang Up](https://www.luogu.com.cn/problem/CF1187G) 来了个真正的按时间分层费用流。考虑一条链的最差情况,容易证明时间消耗最多 $n+k$。点数就是 $O(n(n+k))$ 的。 原图的边有平方代价,可以差分一下变成多条边(都是套路)。直接建立所有的边,边数会达到 $O(mk(n+k))≈5\times10^5$ 级别。 由于选择边的单调性可以动态建图(类似`P2050`),边数可降为 $O\big((n+k)m+nk\big)≈2\times10^4$ 级别。 $1$ 点到达汇的边还要额外加上 $ct$ 的代价。 接下来就是最小费用最大流。[评测记录](https://www.luogu.com.cn/record/33960667) (以接近$9$倍效率优势拿到了最优解) - [P4066 [SHOI2003]吃豆豆](https://www.luogu.com.cn/problem/P4066) 观察吃豆人不能相交的限制,其实可以相交了就交换路线,直接无视这条限制。 但是每颗豆子只能吃一次的限制仍然存在,我们拆点限制容量即可。 一条边容量为 $1$ ,费用为 $1$ 。另一条边容量 $\inf$ ,费用为 $0$。 又能够发现,我们的路径可以由若干个豆子确定。我们可以只在豆子之间连边。 先看起来与前面的题目很像,毒瘤之处在于点的位置是散的而不是紧的。 如果直接两两建边,边数会达到 $O(n^2)$ ,不太行。我们考虑来点剪枝,把边数降下来。 不难发现,某个点左下角的所有点都一定能够到达该点。设 $u$ 的左下角集合为 $S_u$。 我们连边的时候,需要寻找 $v∈S_u$ ,如果存在另一个 $t∈S_u$ 且 $v∈S_t$ ,必然存在 $v\rightarrow t \rightarrow u$ 的路径,我们可以不连 $v\rightarrow u$ 。 这样在随机数据(~~本题数据~~)下表现优秀,但是在构造数据中仍然会得到 $O(n^2)$ 条边。 我们考虑主席树优化二维偏序建图,这需要$O(n\log n)$条边,有理有据但是常数大。 [评测记录] () 由于吃豆人只有两只,所以甚至可以`DP`通过…… - [P3159 [CQOI2012]交换棋子](https://www.luogu.com.cn/problem/P3159) 由于棋子只有两种颜色,可以让所有黑色棋子归位,这样白色棋子自然就也放好了。 考虑一个黑色棋子移动的影响 : 两个方格的移动次数减一。 考虑一条路径,头和尾的移动次数减一,中间的移动次数减二。 我们“只出”,“只入”和“出入”三种走法对一个格子的影响(以及费用)是不同的。 可以把点拆成三个 : $left,mid,right$ 连 $left\rightarrow mid\rightarrow right$ ,边权为 $\lfloor w/2\rfloor$ 这样,一个点完整地从 $left$ 走到 $right$ 会经过两条边,而从 $left$ 到 $mid$ 或者从 $mid$ 到 $right$ 只需要一条边。 需要求解最小交换次数,可以给每条边附加 $1$ 的费用。 还有个问题,如果某个点原来有黑棋,后来没有,或者原来没有后来有,必然产生一次“只入”或“只出”。 如果 $w$ 是奇数,我们把对应的边流量$+1$ 即可(补偿整除损失) 然后源点向原来的黑棋 $mid$ 连边,后来的黑棋 $mid$ 向汇点连边。 各个位置之间按八联通规则连边,跑最小费用最大流即可。 [评测记录](https://www.luogu.com.cn/record/33879105) - [P4452 [国家集训队]航班安排](https://www.luogu.com.cn/problem/P4452) 观察数据性质,已经给出了满足三角不等式的费用和时间矩阵,也就是说我们直飞一定是最优的。 容易想到根据时间分层,但是点数太多效率低下。 观察到请求数量不多,且都由绝对时间限制,这就说明两个请求之间的关系是确定的。 我们给每个请求建立一个点,容量为$1$,点权为净收益。 然后查看所有其他请求是否来得及接,如果来得及,连边费用为 $-$花费。 注意也要与基地连边。 求最大费用最大流即可。[评测记录](https://www.luogu.com.cn/record/33929681) ## 费用匹配 - [P4014 分配问题](https://www.luogu.com.cn/problem/P4014) 这是个经典的带权二分图匹配问题,在中间的匹配边上加上费用,最大费用最大流即可。 由于图较为稠密,且增广路一般较短,建议试试`zkw`费用流。 [评测记录](https://www.luogu.com.cn/record/33933315) - [P3967 [TJOI2014]匹配](https://www.luogu.com.cn/problem/P3967) 多了一问 : 二分图带权匹配的必须边。 懒得分析,由于数据范围小,可以搞一些比较暴力的解法。 直接暴力枚举所有目前在匹配中的边,删去查看带权匹配是否减小。这样需要 $O(n)$ 次匹配。 原来还搞了个 $O(n\log n)$ 次的分治,思维江化了…… [评测记录](https://www.luogu.com.cn/record/34029920) - [P4015 运输问题](https://www.luogu.com.cn/problem/P4015) 加入了流量,带权多重二分图匹配。 [评测记录](https://www.luogu.com.cn/record/33933315) - [P3705 [SDOI2017]新生舞会](https://www.luogu.com.cn/problem/P3705) 先搞个`01`分数规划,将边的权值置为 $a-mid*b$ ,现在就是要判定是否存在匹配的权值总和 $\geq0$。 然后就是带权二分图匹配,跑(实数)最大费用最大流即可。 如果觉得太慢可以转成整数费用流,学习`zkw`,或者学习更加有理有据的带权匹配算法。 [评测记录(EK)](https://www.luogu.com.cn/record/33882633) $\ $ [评测记录(zkw)](https://www.luogu.com.cn/record/33891365) - [P4134 [BJOI2012]连连看](https://www.luogu.com.cn/problem/P4134) 能够发现就是个带权匹配,没听说过2012年引入了一般图带权匹配,先有理有据地猜测这是个二分图。 建立出 $[1,1000]$ 的图,染个色,发现确实是二分图。然而听说 $[1,10^4]$(或者更大) 的图就不是了……出题人你想干啥? 然后跑个二分图带权匹配就是了,注意到$(x,y)$匹配的收益是$x+y$,甚至可以直接把费用设在源汇边上。 [评测记录](https://www.luogu.com.cn/record/33936365) - [P2488 [SDOI2011]工作安排](https://www.luogu.com.cn/problem/P2488) 仍然是二分图带权带容量匹配,只不过费用是分段函数。 观察数据限制发现,这个分段函数是凸的,那么直接给每一段建立一条边,一定会先走前面的边,就已经符合题意了。 求最小费用最大流即可,注意答案存储需要开`long long`。 [评测记录](https://www.luogu.com.cn/record/33951029) - [UVA11613 Acme Corporation](https://www.luogu.com.cn/problem/UVA11613) 如果没有保质期限制,非常简单。 对每一天建点,连源,容量为生产力,费用为(负的)成本; 连汇,容量为最大售出量,费用为单价。 每天连向下一天,费用为 $I$ 容量为 $\inf$ 。 但是本题有保质期限制,所以第 $i$ 天生产的商品不一定能出售给后面的所有时间。 数据范围较小,可以直接转为费用匹配。 对每天分别建立出点入点。分别计算出从第 $i$ 天售给第 $j$ 天的单位收益然后连边,这就方便处理保质期的限制了。 我们要求的不一定是最大流,而是最大费用任意流,所以当费用为负时直接退出即可。 [评测记录](https://www.luogu.com.cn/record/34092522) - [P2053 [SCOI2007]修车](https://www.luogu.com.cn/problem/P2053) 某辆车先修理这一决策,不仅仅会导致这辆车花费等待时间,还会影响到排在后面的车。 我们考虑提前计算贡献。对于某个技术人员,排名**倒数**第 $i$ 的车会让之后(包括自己)的 $i$ 辆车花费 $t$ 的时间等待。 这能够让我们简化状态 : 某辆车,在某个技术人员手中,排名倒数第几。对应的贡献就是确定的。 现在就变成了一个带费用的匹配问题,跑最小费用最大流即可。点数是$O(nm)$,边数是$O(n^2m)$的。 [评测记录(久远)](https://www.luogu.com.cn/record/list?pid=P2053&user=58705) - [P2050 [NOI2012]美食节](https://www.luogu.com.cn/problem/P2050) 和上一题是本质相同的,难点在于数据范围增大了,不能直接跑费用流。 容易发现,如果倒数第 $i+1$ 的匹配位置没有被占用,那么倒数第 $i$ 的位置绝对不会被占用。 `EK`算法每次只会找到一条增广路,我们可以每次增广之后,查看新的匹配,然后把下一个空加入即可。 这样,总点数就是$O(n+m+p)$的,边数也就是$O(n(n+m+p))$。 图比较稠密,推荐使用`vector`。[评测记录](https://www.luogu.com.cn/record/33675346) - [CF863F Almost Permutation](https://www.luogu.com.cn/problem/CF863F) 首先,容易把所有的限制转成某个位置的值 $\in[l_i,r_i]$ 的形式。 然后注意到值域不大,我们可以对每个位置的每种决策(匹配)分别建边。 每个点有$1$的流量,出边连向 $[l_i,r_i]$ 中的各个计数桶。 对于每个桶,代价并不是线性的。这也好办,类似上一题枚举代价差分即可,由于平方是凸函数,一定会先走前面的边。 求最小费用最大流即可。[评测记录](https://www.luogu.com.cn/record/33957476) 本身就有 $O(n^2)$ 条边,无需额外的单调性动态建边优化。若使用区间数据结构则可能需要。 - [P4307 [JSOI2009]球队收益 / 球队预算](https://www.luogu.com.cn/problem/P4307) 每场比赛设置一个点,流量限制为 $1$ ,分别向双方连边,流给谁表示谁赢。 求出某支球队总共需要比赛的场数 $t$ ,假设赢 $a$ 场,则输 $t-a$ 场。 考虑多赢一场造成的花费变化量 : $$(c(a+1)^2+d(t-a-1)^2)-(ca^2+d(t-a)^2)=2ac+2ad+c+d-2dt$$ 不难发现这个值随着$a$的增大而增大。 对于某支球队,算出多赢一场所需的费用,然后一条条连边,表示多赢第……场。(注意已有的胜场) 由于费用递增,费用流一定会依次按照赢场递增走边,这是一定符合状态定义的。 注意到 $\sum t-a$ 仅仅 $O(m)$ 级别,就无需单调性加边优化了。 [评测记录](https://www.luogu.com.cn/record/33952628) - [P4249 [WC2007]剪刀石头布](https://www.luogu.com.cn/problem/P4249) & [CF1264E Beautiful League](https://www.luogu.com.cn/problem/CF1264E) 题意 : 给一个部分确定的竞赛图定向,要求三元环尽量多。 我们不妨最小化非三元环子图,然后用三点子图 $\binom{n}{3}$ 去减。由于其不对称,可能特征更明显,便于统计。 考虑某三点子图不是三元环的情况(请自行画图) : 某个点入度为 $2$ ,某个点出度为 $2$ , 某个点出入都是 $1$。 来到整张图中考虑,能够发现某点若入度为 $k$ ,则能选择出 $\binom{k}{2}$ 个此类子图,而且每个子图只会在入度为 $2$ 的点处计数,不会重复。 对于每条未定向的边,限制流量为$1$,这个流量(入度)可以分到任意一个端点去。 对于每个端点,连向汇。此时的费用不是线性的,由于 $\binom{k}{2}$ 是凸函数所以可以差分。 [评测记录1](https://www.luogu.com.cn/record/33958483) & [评测记录2](https://www.luogu.com.cn/record/33958641) - [P6061 [加油武汉]疫情调查](https://www.luogu.com.cn/problem/P6061) 图的最小环覆盖? 先跑一个`Folyd`。 按照套路把点拆成出入点,某两个点之间的匹配可以看做将两条路径接在一起。 进一步发现,对于一个完美匹配(置换?),按照匹配连接路径之后正好得到若干个环。 那么我们在这个二分图的 $(u,v)$ 之间连边 $dis[u][v]$ ,在 $(u,u)$ 之间连边 $a[u]$ 即可。 这样需要 $O(n^2)$ 条边,有点虚。但是,观察到 $m$ 不大,不妨直接把原图建出来代替这些 $dis$。 但是每个点自己成环,代价(距离)不是 $0$ ,考虑拆成出入点。 源连出点,入点连汇,从入到出免费不限流量,从出点到入点(反向)需要 $a[u]$ 的代价。 [评测记录](https://www.luogu.com.cn/record/33937366) - [UVA12092 Paint the Roads](https://www.luogu.com.cn/problem/UVA12092) **题意** : $n$ 个点 $m$ 条带权边的有向图,要给边染色。 让染色的边形成若干个回路,且每个点都**恰好**属于其中$k$个回路。问最少的染色边权和。 上一题的扩展,直接令每个点的出入度都为 $k$ 即可。 还需要限制每条边只能染一次,这就只能建立原图并拆点了。 [评测记录](https://www.luogu.com.cn/record/34092916) (数据似乎较弱……) - [CF277E Binary Tree on Plane](https://www.luogu.com.cn/problem/CF277E) 容易发现可能的父子关系是一个`DAG`,这就不会出现环。 观察到二叉树的每个点都必选,这就没必要限制流的连续性。(也就躲过了“分流”的难题) 将每个点拆成出入点,入点连汇,容量为$1$,表示必须存在于树中。 源连出点,容量为$2$,表示可以分$2$叉。 各个点之间连边,按照欧氏距离确定费用。 最后求解(实数)最小费用最大流。[评测记录](https://www.luogu.com.cn/record/33929197) - [P4068 [SDOI2016]数字配对](https://www.luogu.com.cn/problem/P4068) 奇怪的题目……要求费用为正?先考虑经典的费用流。 设 $c[i]$ 为第 $i$ 个数的素因子次数和,那么 $(x,y)$ 能配对,当且仅当 $a[x]|a[y]$ 且 $c[x]-c[y]=1$ 由于能匹配的对子 $c$ 都恰好差 $1$ ,能够发现这是个二分图带权带容量匹配问题。 现在有要求费用为正的情况下流量尽量大,由于经典最大费用流算法中,每次按照最长路增广,最长路会逐渐变短。 这是具有单调性的,我们只需要使劲增广直到总费用为负数即可。注意最后一次增广可能只能获得一部分流量。 [评测记录](https://www.luogu.com.cn/record/33937933) - [UVA1411 Ants](https://www.luogu.com.cn/problem/UVA1411) 注意有多组数据,不要像我一样白`WA`两发。 注意到不同的方案中,关于相交的限制是不同的,多个可能的匹配之间的互斥关系十分复杂。 考虑先使用几何知识分析,若有两条相交的线段(灰色),将其调整成不相交的连接方式(黑色),长度一定会变短。  (可以使用三角形两边之和大于第三边证明) 所以,不难得到结论 : 对于一个交错的方案,必定存在一个不交错的方案,连线总长度更短。 由于题目保证有解,我们求解最小费用匹配就得到了答案。 [评测记录](https://www.luogu.com.cn/record/34093520) - [P5331 [SNOI2019]通信](https://www.luogu.com.cn/problem/P5331) 不难发现这是个`DAG`,问题就是最小权路径覆盖。可以转为二分图带权匹配。 直接暴力建边,边数可能达到 $O(n^2)$ ,无法通过。 观察到我们每次都在向一个编号前缀连边,而费用是绝对值,与 $a$ 的相对大小有关,限制相当于二维偏序。 离散化之后主席树优化建边即可。具体来讲,需要维护两颗主席树,一棵点权为 $-a_i$ ,另一颗为 $+a_i$。 连边时,向第一棵的 $[1,a]$ 连边 $+a$ ,向第二棵的 $(a,\max a]$ 连边 $-a$。 这样边数就降为了$O(n\log n)$ ,但是点数也变为了 $O(n\log n)$ ,卡卡常就过了。 [评测记录] () - [P3965 [TJOI2013]循环格](https://www.luogu.com.cn/problem/P3965) 不难发现这张图每个点只有一个出度,就是一个基环内向树森林。若满足“循环”的定义,一定是由若干个环组成。 “环森林”的充要条件就是 : 每个点都只有一个入度,一个出度,这可以视作匹配。 首先拆成出入点,各有 $1$ 的容量。 对于一个点,可以向四个方向(注意边界循环)匹配,若恰好是自己的初始方向,费用为 $0$ 否则费用为$1$。 然后就是二分图带权匹配了,由于费用小建议跑`zkw`。 [评测记录](https://www.luogu.com.cn/record/33951440) - [P4003 无限之环](https://www.luogu.com.cn/problem/P4003) 非常有意思的题目。 不漏水的要求,相当于让相邻格子之间流量尽量大。 可以给棋盘染个色变成二分图,黑的位置连源,白的位置连汇,就能让相邻格子产生流。 考虑对这些形状分类讨论。设 $(f,c)$ 为一条容量为 $f$ ,费用为 $c$ 的边。 由于每个点可能有四个接头,我们对每个位置建立 $5$ 个点,分别为 “上下左右中”,其中“中”限制流量。 下面对于特定朝向的形状进行分析,只需要旋转就能得到所有情况。 -  中向上连一条 $(1,0)$ (不用转),向左右分别连 $(1,1)$ (转一次),向下连 $(1,2)$ (转两次). -  先让中向上右各连一条 $(1,0)$。 考虑顺时针转一次,相当于上面少了一个接头,下面多了一个接头。上向下连 $(1,1)$,类似地有右向左连 $(1,1)$。 能够发现,旋转两次的情况,流量到了左下,费用恰好为 $2$ ,这是自洽的。 -  先让中向上左右各连一条 $(1,0)$。 顺时针旋转一次,相当于左边少了一个接头,下面多了一个接头。左向下连 $(1,1)$,类似地有右向下连 $(1,1)$。 也可以转两次,相当于上面少了一个接头,下面多了一个接头。上向下连 $(1,2)$。 - 发现直线不好建模,但是直线恰好不能转,直接让中向左右各连一条 $(1,0)$。 - 十字形显然转了和没转一样,直接让中向上下左右各连一条 $(1,0)$。 注意需要根据“中”连的是源还是汇,来确定边的方向。 别忘了在相邻的对应方格的对应接头之间连上 $(1,0)$ 边。 然后把讨论在代码里复现,求最小费用最大流。 由于费用很小,增广路较短,多路增广的`zkw`比`EK`快 $20$ 倍。 [评测记录](https://www.luogu.com.cn/record/33949020) ## 不好归类的题目 - [P2604 [ZJOI2010]网络扩容](https://www.luogu.com.cn/problem/P2604) 第一问就是最大流。然后将源点的流量限制为 $\text{最大流}+k$ 将每条边复制一份作为“扩容边”,容量为 $\inf$ ,费用为 $w$ ,求最小费用最大流即可。 [评测记录(久远)](https://www.luogu.com.cn/record/15169377) - [P2517 [HAOI2010]订货](https://www.luogu.com.cn/problem/P2517) 从第 $i$ 天连向汇,容量为 $U[i]$ ,表示卖出。 从源连第 $i$ 天,容量为 $\inf$ ,费用为 $D[i]$ ,表示购入。 从第 $i$ 天连向第 $i+1$ 天,容量为 $S$ ,费用为 $m$ ,表示存储。 求最小费用最大流即可。 [评测记录](https://www.luogu.com.cn/record/33949949) 奇怪的是 $n\leq 50$ ,甚至有`DP`解法……建议加强到 $n\leq 10^3,S\leq 10^6$ - [P3358 最长k可重区间集问题](https://www.luogu.com.cn/problem/P3358) & [CF164C Machine Programming](https://www.luogu.com.cn/problem/CF164C) 很像朴素的匹配问题 : 每段只能匹配 $k$ 个区间。 我们向每个区间连边,问题来了,对于一段区间我们不好限制必须要整体选择。 一个关键的性质是 : 可以把最优解划分成选择若干次**不交**的区间集合的形式。能够发现选择 $k$ 次的最优方案就是答案。 考虑每个区间拆成出入点,之间容量为 $1$ ,费用为 $len$。 按左端点排序,每个区间向着后面不交的区间连边,容量为$\inf$,费用为 $0$ 。然而可能产生 $O(n^2)$ 条边。 注意到“不交”具有单调性,我们给每个区间**入点到下一个入点**之间新增一条边,容量为 $\inf$ ,费用为 $0$ ,表示经过但不选择。 这样就只需要向着后面**第一个**不交的区间连边了,边数降为 $O(n)$。 容易发现,一个流的意义就是选择一个不交的区间集合。 然后每个区间的入点都连源,容量为$1$,出点连汇,容量为$1$,表示可以任意开始结束。源汇的容量均为$k$。 求最大费用最大流即可。 [评测记录1](https://www.luogu.com.cn/record/33944932) & [评测记录2](https://www.luogu.com.cn/record/33945028) - [P3357 最长k可重线段集问题](https://www.luogu.com.cn/problem/P3357) 和上一题就两个区别 : 长度的计算方式变了。有可能出现垂直于 $x$ 轴的线段。 我们将所有的位置 $*3$ 然后略微移动左右端点来模拟开区间即可。(注意垂直于$x$轴的情况) [评测记录](https://www.luogu.com.cn/record/33945261) - [P3980 [NOI2008]志愿者招募](https://www.luogu.com.cn/problem/P3980) 神仙题.jpg 同样很像朴素的匹配问题,考虑对每天建立点限制流量,发现志愿者只能够向一个区间整体贡献,不好处理。 换一种方法建图,将每天**串**起来。 考虑只有一种志愿者怎么办,显然需要 $\max a[i]$ 人。 而我们的网络流,串联边的规则是流量取 $\min$ ,我们可以取一个足够大的 $H>\max a$ ,将流量置为 $H-a[i]$ ,这样就相当于取 $\max$ 了。 最终的目标就是让最大流达到 $H$ ,在没有帮助的情况下,流量是 $H-\max a$。 考虑志愿者能够提供怎样的帮助 : 给 $[l,r]$ 的边一起扩大若干流量。 我们就可以从 $l_i$ 连向 $r_i+1$ ,容量为 $\inf$ , 费用为 $c_i$ ,能够发现走这条边等效于给 $[l_i,r_i]$ 的边一起扩大。 然后跑一个最小费用最大流即可。[评测记录](https://www.luogu.com.cn/record/33946909) 有另一种更加循规蹈矩的方法,通过线性规划推式子转费用流。 设 $P_i$ 为第 $i$ 天招募志愿者的数量, $X_i$ 为第 $i$ 种志愿者的数量,可以对于 $k∈[1,n]$ 得到如下不等式组: $$X_k=\sum\limits_{k∈[l_i,r_i]}X_i\geq A_k$$ 不等式不便分析,考虑添加松弛变量变为等式,设 $D_i$ 为第 $i$ 天多余的人数。 $$-D_k+\sum\limits_{k∈[l_i,r_i]}X_i= A_k$$ 将第 $k$ 组与第 $k-1$ 组等式相减,这里我们认为 $A_0=A_{n+1}=0$ $$D_{k-1}-D_k+\sum\limits_{k∈[l_i,r_i]}X_i-\sum\limits_{(k-1)∈[l_i,r_i]}X_i= A_k-A_{k-1}$$ 考虑容斥,$k∈[l_i,r_i]$ 且 $(k-1)\not∈[l_i,r_i]$ 相当于要求 $l_i=k$。$k\not∈[l_i,r_i]$ 且 $(k-1)∈[l_i,r_i]$ 相当于要求 $r_i=k-1$。 $$D_{k-1}-D_k+\sum\limits_{l_i=k}X_i-\sum\limits_{r_i=k-1}X_i= A_k-A_{k-1}$$ $$A_{k-1}-A_k+D_{k-1}-D_k+\sum\limits_{l_i=k}X_i-\sum\limits_{r_i=k-1}X_i=0$$ 如果我们把每个式子看做一个点,正数表示流入,负数表示流出,等式就代表着流量平衡。我们能得到如下的建图方法。 - (类似上下界网络流)钦定每个点的流量总和为常数 $A_{k-1}-A_k$ 。根据其正负,从源或汇向点 $k$ 连边。 - 观察到 $D_k$ 会在 $k+1$ 处正一次,在 $k$ 处负一次,从 $k$ 向 $k+1$ 连边,容量为 $\inf$ ,表示 $D$。 - 观察到 $X_i$ 会在 $l_i$ 处正一次,在 $r_i+1$ 处负一次,则从 $r_{i+1}$ 向 $l_i$ 连边,容量为 $\inf$ ,费用为 $c_i$。 然后就是最小费用最大(可行)流。由于未知的原因,比上一种方法明显低效。[评测记录](https://www.luogu.com.cn/record/33947330) - [CF802C Heidi and Library (hard)](https://www.luogu.com.cn/problem/CF802C) 神仙题.jpg 观察一本书的行为 : 若 $j,i(j<i)$ 天都需要,如果一直持有该书,则只需要付一次钱,否则需要两次。 “持有”这一状态不包含流量的改变,不好建模。不妨考虑叠缩,视作可以在昨天**售出**上次供给的同类书,并且**总会**再次购入。 这样就使得我们的策略一定合法。 将每一天拆成 : 售卖处 $r$ ,购书处 $u$ ,和回收站 $v$ 。以 $(f,c)$ 表示容量为 $f$ ,费用为 $c$ 的一条边。 每天的顺序是: 先卖,再买,然后回收。 - $S\rightarrow u=(1,c_{a})\ $ 表示购入。 - $u\rightarrow v=(1,0)\ $ 表示可以在当天就丢弃。 - 设第 $i$ 天上一次需要同样的书是第 $j$ 天. $r_{i}\rightarrow v_j=(1,-c_{a_i})\ $ 表示售出。 - $v\rightarrow T=(1,0)\ $ 表示该天购入的书只能够回收一次,丢或者卖二者只能选其一。 - $u_i\rightarrow r_{i+1}= (k,0)$ 表示在书架中保存。 - $r\rightarrow u=(k-1,0)\ $ 表示在书架中保存,由于新书购入需要一个位置,这里是 $k-1$。 注意,一定要先卖后买,这样才能限制一定是旧书,防止买完就卖。 不难发现,可以将 $r_i$ 和 $u_{i-1}$ 合并。 观察这个模型,若某本书当天没有被扔掉,一定会一直待在书架里占用位置,直到被卖掉。 求最小费用最大流。 [评测记录](https://www.luogu.com.cn/record/34034524) 我们巧妙地在回收站包含了信息,而利用题目中的要求必须满足的性质将状态缩减,把不同的书当做同样的流量处理。 类似的题 : [CF132E Bits of merry old England](https://www.luogu.com.cn/problem/CF132E) & [评测记录] () 输出方案的话,记录下每个售出和购入,将能串的串在一起,然后按时间顺序扫描即可。 # 3.上下界网络流题目泛做 可能会用 $(u,v,[l,r])$ 表示一条从 $u$ 到 $v$ 的,容量在 $[l,r]$ 之间的边。 用 $(u,v,[l,r],c)$ 表示一条从 $u$ 到 $v$ 的,容量在 $[l,r]$ 之间,费用为 $c$ 的边。 - [P5192 Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流](https://www.luogu.com.cn/problem/P5192) 考虑对每天分别拆点,流量限制为 $D$ ,向右侧连流量限制为 $[L,R]$ 边, 右侧点限制为$[G,\inf]$。 然后跑有源汇上下界最大流即可。[评测记录](https://www.luogu.com.cn/record/34036779) - [P4843 清理雪道](https://www.luogu.com.cn/problem/P4843) 观察“每条雪道至少被清理一次”的要求,相当于流量至少为 $1$ 。建立 `DAG` 并将限制设为 $[1,\inf]$ 即可。 接下来就是有源汇上下界最小流。 [评测记录](https://www.luogu.com.cn/record/22641061) - [P2304 [NOI2015]小园丁与老司机](https://www.luogu.com.cn/problem/P2304) 第一问考虑`DP`,注意到可能的路径并非`DAG`,需要仔细考虑。 能够发现有每个 $y=c$ 上不超过 $1000$ 个点限制,这指示我们采用按 $y$ 分层的比较暴力的做法。 设 $f(i,j)$ 为到达 $y=i$ 的从上到下第 $j$ 棵树许愿,之前能许愿的最多次数。 转移让前面的树贡献,每棵树只会有“上,右上,左上”三种转移方式。拿桶搞一搞就容易得出转移目标。 接下来是同行转移,我们可以非常暴力地枚举进入点和离开点$(u,v)$,分类讨论。 - $u=v$ : 直接离开。 - $u<v$ : 可以走完所有 $v$ 左边的树。 - $v<u$ : 可以走完所有 $v$ 右边的树。 设一行的点数为 $d$ ,这样的复杂度是 $O(\frac{n}{d}d^2)=O(nd)$ 的。 注意,对于每次转移,还需要记录最优方案。反向递归这些方案回答第二问。 我们按照转移顺序反向标记出那些点可能达到最优解,找出所有包含在最优转移中的“左上,右上,上”边,它们组成一个`DAG`。 接下来就是上一题了,求有源汇上下界最小流即可。 [评测记录] () - [P4043 [AHOI2014/JSOI2014]支线剧情](https://www.luogu.com.cn/problem/P4043) 有源汇上下界最小费用可行流。 每条边至少被经过一次,流量限制就是 $[1,\inf]$。 然后把有源汇上下界可行流套上费用流就做完了。(注意要计算初始流的费用) [评测记录](https://www.luogu.com.cn/record/34037671) - [P4553 80人环游世界](https://www.luogu.com.cn/problem/P4553) 容易发现只是在`P4043`的基础上把点的容量限制定死了。 [评测记录](https://www.luogu.com.cn/record/34039546) - [P2469 [SDOI2010]星际竞速](https://www.luogu.com.cn/problem/P2469) 由于引力大小的限制,若只考虑高速航行,这图是个`DAG`。 能够发现,空间跳跃的花费和起点无关,我们可以将方案等效抽象成以从起点跳跃开头的若干条路径。 于是就可以转化为和上面类似的`DAG`遍历问题。 求最小费用可行流。 [评测记录](https://www.luogu.com.cn/record/34040252) 由于限制点不相交,还能转化成最小代价路径覆盖。 首先让每个点自成一条路径,此时代价是 $\sum A$。 仿照最小路径覆盖,建立二分图,一条匹配边就代表将两条路径合在一起。 所以从 $u\rightarrow v$ 建立一条 $\text{原边权}-A[v]$ 的边,表示合并之后代价的变化量。 但此时我们求的并不是最小费用最大流,而是最小费用合法流。 由于费用流中最短路一定会逐渐变长,我们只需要增广直到最短路为正即可。 比起上一种方法,不需要上下界,代码更短,跑得也要略快一些。[评测记录](https://www.luogu.com.cn/record/34040737) - [P4542 [ZJOI2011]营救皮卡丘](https://www.luogu.com.cn/problem/P4542) ~~去日本旅游的黑猫警长xswl~~ 反正所有的据点最终一定会被干掉,多条路径之间,我们不需要关心相对顺序。 只需要限制每条单独的(摧毁)路径必须按顺序进行,最后把各个路径归并一下即可。 问题在于,目前占领了多少据点,可能影响到我们走的最短路。 先使用 `Folyd` 预处理出 $dis[u][v]=$ 只经过 $\leq v$ 的点,从 $u$ 到达 $v$ 的最短路。 如果一个人上一次摧毁 $x$ ,下一次摧毁 $y$ ,那么说明 $\leq y$ 的据点已经可以任意经过,最短路是$dis[x][y]$。 然后就是一个`DAG`的最短 $k$ 路径覆盖问题,类似于上一题。 同样也可以使用费用匹配求解路径覆盖。这里 $1$可以接 $k$ 条路径,所以容量是 $k$ ,其他点的容量(出度限制)都是 $1$。 [评测记录](https://www.luogu.com.cn/record/34041435) - [P4311 士兵占领](https://www.luogu.com.cn/problem/P4311) 直接建立矩阵对应的结构不好做,考虑从行“剥离”总和贡献到列。 给每行每列都建立一个点,有容量下界限制。 $S\rightarrow$行, 列$\rightarrow T$ ,中间无障碍的地方在对应行列之间连边 $[0,1]$ 即可。 然后是一个有源汇上下界最小流。 [评测记录](https://www.luogu.com.cn/record/34042348) - [P4194 矩阵](https://www.luogu.com.cn/problem/P4194) 题面用人话说就是 : 给出矩阵 $A$ ,要求构造同样大小的,元素都在 $[L,R]$ 内的矩阵 $B$ 。 使得矩阵 $C=A-B$ 每行的和以及每列的和的 $\max$ 最小。 考虑二分答案。绝对值的限制可以转化为 : 每行每列的和在 $[-K,K]$ 内。 减去已经确定的 $A$ 的贡献,就能得到 $B$ 每行每列的和的范围。 给每行每列都建立一个点,并如上所述限制流量。 直接建立矩阵的对应结构并不好处理,考虑从行“剥离”总和贡献到列。(类似`P4311`) $S\rightarrow$行, 列$\rightarrow T$ , 然后每行每列之间连边 $[L,R]$ 即可。 跑有源汇上下界可行流来判定。注意会有负数流量,但是会被自动处理掉。 [评测记录](https://www.luogu.com.cn/record/34044274) - [P1251 餐巾计划问题](https://www.luogu.com.cn/problem/P1251) 个人认为是网络流24题中最好的前三道。 把每天拆成三个点 : 上午,下午(新),下午(旧) 从 $S$ 连到每天上午,容量为 $\inf$ ,费用为 $p$ , 表示购买餐巾。 从 上午 到 下午(旧) 连边,限制容量恰好为 $a$ ,费用为 $0$ ,表示需要用掉这么多餐巾。 从 上午 到 下午(新) 连边,容量 $\inf$ ,表示没用完的餐巾可以存储。 每天都有快洗部和慢洗部,分别向 $n$ 或 $m$ 天后的上午连边,容量 $\inf$ ,费用为 $f$ 或 $s$。 从 下午(旧) 分别连边到 $T$(表示丢弃) ,快洗部,慢洗部,,容量均为 $\inf$ ,费用为 $0$ 。(容易发现最优方案中不存在延期送洗) 不难发现 下午(旧)/快洗部/慢洗部 三个点可以合并, 上午/下午(新) 两个点可以合并。 求最小费用可行流即可。由于费用只有两种,写个多路增广即可有理有据地获得大幅效率提升。 [评测记录(普通)](https://www.luogu.com.cn/record/34045033) & [评测记录(多路增广)](https://www.luogu.com.cn/record/34045790) - [CF1288F Red-Blue Graph](https://www.luogu.com.cn/problem/CF1288F) 我们可以把`R`边看做从左向右流,`B`边看做从右向左流,`U`边看做不流。 则对于原图中的每条边 $(u,v)$ ,分别建边 $(u,v,[0,1],r),(v,u,[0,1],b)$。 一条`R`边会给左边的点流量 $-1$ ,给右边的点 $+1$。`B`边则给左边 $+1$ ,右边 $-1$ 。 - 对于左半部: 对于`R`点,要求出流量(`R`)严格大于入流量(`B`),则连边 $(S,R,[1,\inf],0)$ 对于`B`点,要求入流量(`B`)严格大于出流量(`R`),则连边 $(B,T,[1,\inf],0)$ - 对于右半部: 对于`R`点,要求入流量(`R`)严格大于出流量(`B`),则连边 $(B,T,[1,\inf],0)$ 对于`B`点,要求出流量(`B`)严格大于入流量(`R`),则连边 $(S,R,[1,\inf],0)$ 对于`U`点,总是无要求,则连边 $(U,T,[0,\inf],0),(S,U,[0,\inf],0)$ 然后求最小费用可行流,费用只有两种,多路增广会快。 [评测记录](https://www.luogu.com.cn/record/34048792) - [CF708D Incorrect Flow](https://www.luogu.com.cn/problem/CF708D) 对于原图的边 $(u,v,c,f)$ , 考虑分段讨论可以采取怎样的变化。 - 若$f\leq c$ - 反向流动 : 容量为 $f$ (真正的流不能小于$0$) ,费用为 $1$ 。 (代表`f--;`) - 正向流动① : 容量为 $\max(c-f,0)$ (无需调整$c$的部分) ,费用为 $1$ 。 (代表`f++;`) - 正向流动② : 容量为 $\inf$ (需要调整$c$的部分) ,费用为 $2$ 。 (代表`f++,c++;`) - 若$f>c$ 能够发现至少有 $f-c$ 的花费,这部分预先计算,便于后面的分析。 - 反向流动① : 容量为 $f-c$ ,费用为 $0$ (被预先计算)。 (代表`f≤c`之前的`f--;`或`c++;`) - 反向流动② : 容量为 $c$ (真正的流不能小于$0$) ,费用为 $1$ 。(代表 `f≤c` 之后的 `f--;` ) - 正向流动 : 容量为 $\inf$ ,费用为 $2$ 。(代表`f++,c++;`) 对于原图中已有的流量,连边 $(u,v)$ 并限制流量恰好为 $f$。 求上下界最小费用可行流即可。 [评测记录](https://www.luogu.com.cn/record/34049827) - [CF704D Captain America](https://www.luogu.com.cn/problem/CF704D) 不妨设 $r>b$ ,现在我们的目标就是让尽量多的盾牌染成蓝色。 考虑给每行每列分别建立点,一个 $(i,j)$ 的染色操作就相当于给第 $i$ 行和第 $j$ 列各增加 $1$ 单位流量。 绝对值的限制可以视作上下界,跑上下界最大流即可。 出题人有点猛,直接搞了 $10^5$ ,可能需要卡常数。 [评测记录](https://www.luogu.com.cn/record/34051906) - [UVA1104 芯片难题 Chips Challenge](https://www.luogu.com.cn/problem/UVA1104) 1. 任意行或列的部件数不能超过整个芯片总部件的 $A/B$ 这个限制。 没有什么好的处理方法,也不存在单调性,只能考虑枚举芯片总部件数,这样能够确定行和列的限制。 现在转化成了若干个这种问题 : 限制每行每列最多 $lim$ 个,问最多能放置多少个。 直接枚举需要 $O(n^2)$ 次判定,太慢了。 考虑我们枚举的芯片总部件给了这张图传了什么信息,不难发现就**只有**对于行的限制。 而行的容量最多 $n$ ,我们直接 $O(n)$ 枚举这个限制,然后算出合法的总部件数就好了。 - $x$ 行 $x$ 列元件数量相同。 用经典的网络流并不好直接控制,可以使用循环流。 每行每列拆一个点,行列之间按照能放元件的位置连边 : 若已经有元件,则流量限制为 $[1,1]$ 。若没有但是可以放置,则流量限制为 $[0,1]$ 。 最后,从列向行连一条边,限制为 $lim$ ,这样可以保证从列流出多少,行就要收回多少,且一行的流量不超过 $lim$。 图大概是这样子,要使得满足流量守恒的户条件下,红色边的总流量尽量大:  给红色边加 $1$ 的费用,问题就可以转化成最大费用循环流了。注意要使用技巧处理掉正环。 由于费用只有 $0,1$ 最短路可以 $O(n)$ 做,并加上多路增广。 由于流的总量是 $O(n^2)$级别的,估算了一下复杂度上界为 $O(n^4)$ ,这就很稳了。 [提交记录](https://www.luogu.com.cn/record/34071822) 还有一种不需要神仙模板的人类智慧做法。 注意到我们如果仅仅把放置当做流量,“能否放置”和“行列等量”很难兼顾。 不妨把放置和不放置都记作流量,然后给放置附上费用引导决策。 行列分别建点,形成二分图。源连行,列连汇,容量 $n$。 第 $i$ 行连第 $j$ 列,容量为所枚举的限制 $lim$ ,费用为 $1$。表示放置的个数,由于直接连边,自然满足行列等量。 对于可决策的区域 $(i,j)$ , 从行 $i$ 连到列 $j$ ,容量为 $1$ ,费用为 $0$ ,表示不放置。 对于**必须不放置**的区域 $(i,j)$ , 从行 $i$ 连到列 $j$ 。 接下来可以选择使用上下界,限定流量恰好为 $1$,可是你会发现新的图中有正环,还是得消环。 另外一种神奇的做法是 : 容量为 $1$ ,费用为一个大于 $n\times n$ 的数 $M$ ,这样就会绝对优先地走这些边。 如果满流,且所有 $M$ 边满流,且 $lim$ 自洽,则合法。 [提交记录](https://www.luogu.com.cn/record/34070971) 随手一写居然两种做法都`1A`了,有点感动。 - [UVA1659 帮助小罗拉 Help Little Laura](https://www.luogu.com.cn/problem/UVA1659) **题意** : 给定一个平面上的一些有向线段,涂色费用为 $dx-y$, 其中 $d$ 为边的长度(实数), $x,y$ 为给定参数。 环路的涂色费用为各边涂色费用和。找出一些环路,使得这些环路边不相交,且涂色费用总和最大。 最大费用循环流的模板题。直接求解最大费用无源汇可行流会遇到正环,可以使用和“负环费用流”类似的方法。 也即 : 把原图的 $(u,v,cap,len)(len>0)$ 替换成 $(u,v,[cap,cap],len),(v,u,[0,cap],-len)$。 意思就是先把所有的正权边强制流满,然后建立反向边来退流。 接着就是上下界无源汇最小费用可行流,不难发现图中没有正环了。 这个题浮点数不开`SPJ`,手动加`1e-7`才能通过…… [评测记录](https://www.luogu.com.cn/record/34097870)