网络流/二分图相关笔记(应用篇) 更新于 2026/7/10 11:13:22 作者

command_block

请配合 : 网络流/二分图相关笔记(干货篇) 食用,否则可能无法理解某些内容。

1.网络最大流题目泛做

可能会用 $(u,v,f)$ 表示一条从 $u$ 到 $v$ 的,容量为 $f$ 的边。

最大流建模

把流当成移动,路径,选择等等之类。

• P2472 [SCOI2007]蜥蜴

  题意 : 一个矩阵中有若干个石柱,每个石柱都有自己的耐久度。

  现在有一些蜥蜴站在部分石柱上,蜥蜴可以跳到欧几里得距离不超过 $d$ 的地方。

  蜥蜴每次起跳,脚下的石柱都会失去一点耐久,耐久为$0$则石柱损毁,不能落脚。

  问最多能有多少条蜥蜴能够跳出边界。

把蜥蜴的移动当成流,耐久当成容量。

每个石柱需要限流,拆成出入点,之间连上限制。

蜥蜴一开始待在入点。从原点向有蜥蜴的入点连边,容量为$1$。

根据跳跃条件,从出点向其他石柱的入点连边,容量为$\text{INF}$.

能跳出边界的地方,出点向汇点相连,容量为$\text{INF}$.

评测记录

• P2766 最长不下降子序列问题

先用朴素DP求出 $s$。

然后查看 $f[i]\rightarrow f[j]$ 是否是最优转移,如果是,连上一条边。这样能够保证我们的一条流对应一个最长不降子序列。

每个位置拆点限制流量为 $1$ 。第三问就把 $1,n$ 的限制改改。

然后将 $f[i]=1$ 的位置入点接源, $f[i]=s$ 的位置出点接汇,求最大流即可。

评测记录(久远)

• P2754 [CTSC1999]家园 / 星际转移问题

发现在时间不同时,能走的转移是不同的,考虑按照时间分层。

如果在对应时间有一辆飞船从 $u$ 到 $v$ ,则把该层的 $u$ 连向下一层的 $v$ 。

可以证明,若有解,每经过 $n$ 个单位时间至少运送一个人,这样时间的上界是 $n(k+1)$。

我们可以枚举时间,每次新增一层然后增广,如果超过 $n(k+1)$ 层还没有流完,则无解。

评测记录

• P3163 [CQOI2014]危桥

首先,往返可以看做走双倍次数。

我们按照桥的容量建边,然后分别限制两个源汇的流量,这些都是经典操作。

现在跑最大流,出现了两个问题:

• ①可能有些流从 $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$ 后,一种流被反向了,现在是同向,则会一并受到限制。

评测记录

• P5029 T'ill It's Over

容易发现,每节蜈蚣的最优决策都是相同的,我们直接把 $n$ 当做流量即可。

对于每种光明程度,分别建立一个点,源点连 $1$ ,汇点连 $k$。我们的目标是让尽量多的流量来到 $k$。

能够发现,所有的操作都是从一个区间连向另外一个区间,使用一上一下两颗线段树加虚点优化建边即可。

点数是 $O(k+m)$ ,边数是 $O(m\log k)$ ,由于数据随机, Dinic 求最大流就已经足够快了。

评测记录

匹配问题

这类问题把源当做物品,把汇当做盒子,流的意义是匹配(决策)。

• P3386 【模板】二分图匹配

二分图的定义见第二节。

我们把左部点设为源,右部点设为汇。每个点只能连一次,所以源汇的容量都是$1$.

把多个点变成源并限制流量 : 从大源给每个小源分别连一条钦定流量的边。

连边可以变成左部点到右部点的一条有向边。

容易理解这些流和匹配是等价的。

有一个结论是Dinik跑经典二分图匹配的复杂度是$(n\sqrt{m})$的。

评测记录

• P2055 [ZJOI2009]假期的宿舍

把在学校的人匹配到床上,如果最大匹配$=$总人数,就有解。

具体方法:建立二分图,左边是人,右边是床,每个人向能用的床连边。

评测记录(久远)

• P2763 试题库问题

  题意 : 你有$m$个干员,每种干员会做的工作已知。一个干员不能同时做两份工。

  $n$ 种工作各自都有需要的人数,问如何分配能满足人手需要。

右侧带容量的二分图匹配。评测记录(久远)

• P3254 圆桌问题

能发现等价于两侧都带容量的二分图匹配。评测记录(久远)

• P4251 [SCOI2015]小凸玩矩阵

考虑二分答案 $lim$ ,这样大于 $lim$ 的位置才被我们考虑。

现在的问题是能否找出 $k$ 个位置满足每行每列都不矛盾。

这可以看做一个二分图匹配问题,行和列分别为左右部点,若某行某列能放置则连边,这样就能满足“一行只对应一列”的条件了。

评测记录

• P2402 奶牛隐藏

先跑Folyd。然后二分时间$lim$,这时只有距离$\leq lim$的两个点能够互相通达。

我们要把牛分到牛棚里面去,直接二分图匹配即可。

评测记录(久远)

• CF852D Exploration plan

仍然考虑二分时间,判定条件变成了最大匹配$\geq m$。评测记录

• CF546E Soldier and Traveling

每个点上的士兵只能留在自己,或者向相邻的点移动。考虑拆成出入点变为二分图。

从源点连向入点,容量为初始时的人数。从出点连向汇,容量为结束是的人数。

然后对于每条边,从对应入点连向对应出点,边权为 $\inf$。每个点的出入点之间也连 $\inf$ 表示停留。

求最大流。如果初始和结束的总人数不同,或者不满流,则为无解。否则查看反向边的流量输出构造。

评测记录

• CF628F Bear and Fair Set

差分一下能够发现,这些限制本质上是把 $[1,b]$ 分成了若干段,然后分别限制数的个数。

对于每一段,限制总流量为数的个数。我们分别计算模 $5$ 余 $0...4$ 的数的个数,向对应的 $5$ 个收集节点连边。

如果最大流是 $n$ 则说明有解,否则无解。

评测记录

• P3425 [POI2005]KOS-Dicing

考虑二分或者枚举,问题转化成判定所有人都赢不超过 $lim$ 次的情况下存不存在合法方案。

给每场比赛新建一个点,从源连一条边,限制流量为 $1$,表示只能有一方胜出。然后连向比赛双方。

每个人连向汇点,流量限制为 $lim$ ,若满流则表示有解。

构造方案可以查看比赛的流给了哪一方。

评测记录

• P1231 教辅的组成

  题意 : 这是一个三分图。第一层和第二层之间有若干对应关系,第一层和第三层之间也有若干对应关系。同层之间无关系。

  如果找出三元组 $(x,y,z)$ 使得其分别属于一二三层,而且 $x$ 与 $y,z$ 都有对应关系,则称为好的。

  如果每个点只能用一次,求最多能组成的好的三元组的个数。

初看起来像三分图匹配,但是由于二三层之间无关系,还是能够网络流解决。

把第二层连汇,第三层连源,权值为$1$。中间放第一层,对应关系就是中间的边。

容易发现一条流就对应一个好的三元组。

评测记录(久远)

• P2825 [HEOI2016/TJOI2016]游戏

先考虑没有硬石头的情况。相当于不能在同一行或同一列放置两个炸弹。

类似P4251,可以看做一个二分图匹配问题。

若考虑硬石头,可以视作把完整的行/列分成了若干互不影响的段,我们按段的编号建立二分图即可。

评测记录

• P6517 [CEOI2010 day1] alliances

这是个方格图,先黑白染色变成二分图。若没有人类不杠的限制,直接跑二分图多重匹配即可。

能够发现,若不杠又需要两个邻居,一定是一横一竖。我们只需要把人类拆成两个点,一个接一个横,另一个接一个竖即可。

查看匹配情况输出方案。 评测记录

• P3153 [CQOI2009]跳舞

先考虑 $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)$ 之间按照意义连边即可。

评测记录

• P3324 [SDOI2015]星际战争

时间这种自带$\max$性质的东西,一般需要二分转化。

二分之后,每个激光武器就相当于针对每个机器人拥有了一定量的“输出值”可以随意分配。

具体地说,每个激光武器的初始容量为 $B[i]*t$ ,向能攻击的机器人连边,机器人到汇的容量是 $A[i]$。

如果最大流满流则说明可以在 $t$ 时间内完成。由于是实数,可能需要扩大 $10^5$ 倍再使用long long。

评测记录

• P5038 [SCOI2012]奇怪的游戏

这是个方格图,首先考虑黑黑白染色。每次我们只能对一个黑色的格子和一个白色的格子同时$+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$ 是否可行。

我们可以计算出每个点需要加多少次,不难发现两个位置都加一的规则就是二分图带容量匹配。

评测记录(久远)

• P2570 [ZJOI2010]贪吃的老鼠

神仙题.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$ ,安排出一组满足时间不交的旧方案,这样就建立了双射。

直接求最大流即可。评测记录

• P5786 [CQOI2008]传感器网络

考虑把每个点匹配给自己的父亲,建立二分图,左侧为出点,右侧为入点。

考虑二分/枚举,接下来就需要判断负载级别为 $k$ 是否可行。

每个点只能有一个父亲,于是限制左侧容量一律为 $1$。每个点最多有 $k$ 个儿子,于是限制右侧容量一律为 $k$。

注意,控制中心的流量不受限制。如果满流则有解。

接下来考虑字典序,不难想到逐位贪心。先钦定若干匹配,然后在剩下的图中跑匹配,看看是否满流。

逐位枚举,需要 $O(n^2)$ 次匹配(单流增广)。

[评测记录] ()

• P4382 [八省联考2018]劈配

我们考虑将选手匹配向导师。

同阶志愿对于某个选手是没有区别的,所以可能存在后面的选手让前面的选手反悔的情况。

对于每个选手,逐次检查每阶志愿中是否有可能空位,若有,则连向该阶志愿的所有导师并增广。这会留下反向边,自然处理了反悔操作。

现在问题在于如何判断某个导师是否可能有空位。等价于问某个导师的点到汇点是否有增广路,从汇点反向搜索即可(注意,图上有环,不能瞎搜)。

这样需要 $O(n)$ 次残量网络上的(单流)增广和BFS,复杂度上界是 $O(n^2C)$ 的。

接下来是第二问,不难发现某个前缀所造成的导师“填满”状态是固定的。

二分一下新的排名,然后查看是否能满足要求即可。这部分复杂度是 $O(n^2\log n)$

评测记录

• CF793G Oleg and chess

这是一个经典的车放置问题,可以二分图匹配解决,但是连$O(n^2)$条边显然无法承受。

考虑优化建边,不难想到主席树+扫描线,这样点数和边数都是 $O(n\log n)$ 的。

另一种更加牛逼的做法是 : 利用题目中黑矩形不交的性质,从每个矩形的上下边界向外延伸(遇到障碍就停止),能够将整个图的空位剖分成 $O(n)$ 个矩形。

_______________________
    ###________________
    ###___________##
    ###     ####  ##
____###_____####__##___
____________####_______

空矩形只有 $O(n)$ 个是因为每个黑矩形只会贡献 $O(1)$ 条边界。

对于每个空矩形,相当于从左部点的一个区间连向右部点的一个区间,我们分别维护两颗线段树即可。

这样边数还是 $O(n\log n)$ ,点数是 $O(n)$ 的 (似乎常数有点大)。

至于这些矩阵怎么划分,反正 $n=10^4$ ,暴力扫描线就是了。评测记录

• CF212A Privatization

神仙题,找不到题解,看wxh神的代码学了一下 /kel。看不懂结论,咕咕。

https://codeforces.com/contest/212/submission/34274620

棋盘染色

对于一个棋盘,像国际象棋那样染成黑白两色,容易发现这是个二分图。

由于这类题实在太多,这个套路又比较简单,就不单独归类了。

最小割建模

• P2774 方格取数问题

  题意 : 给出一个带权值棋盘,相邻的两个东西不能选,问能选的最大总和。

把网格像国际象棋那样染成黑白两色,容易发现这是个二分图。

这里“不能选”的限制有点类似割,我们考虑最小割。即割的尽量少,保留的尽量多。

相邻的不能选,相当于割断二分图。

我们把中间边设为INF,这样不会被割掉。

然后源汇均按权值连边即可。

评测记录(久远)

• P5039 [SHOI2010]最小生成树

根据 Kruskal ,其他边$-1$相当于让自己$+1$。

考虑 Kruskal 的排序建立过程,把小于 $Lab$ 的边拿出来建图,若$Lab$两端不连通,则可以被选入最小生成树。

使得某条边 $\geq Lab$ 而不被拿来建图的花费是 $Lab-w$ ,以此为边权求最小割即可。

评测记录

• P5934 [清华集训2012]最小生成树

和上一题类似,甚至不需要推结论。

对于最小生成树,取出权值小于关建边的边跑一次最小割。

对于最大生成树,取出权值大于关建边的边跑一次最小割。

评测记录

• P2598 [ZJOI2009]狼和羊的故事

建篱笆就是最小割,源连狼,羊连汇,容量为$\inf$。格子向四连通方向连容量为 $1$ 的边,求最小割。

评测记录(久远)

• P6094 [JSOI2015]圈地

可以让源连南南的房子,强强的房子连汇,容量均为价钱。

每个格子向四连通的方向连对应墙代价的边。

能够发现,一个割就对应着一种合法的方案。(割了房子就代表不卖,割了墙就代表造墙)

将所有可能的收益求和,减去最小割即为答案。 评测记录

• P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查

注意到意见只能有两种,我们可以以 $S,T$ 集来区分。

朋友之间连一条双向边,权为 $1$ ,表示如果朋友不在一个集合内需要割断 $1$ 的代价。

对于持有 $\sqrt{}$ 意见的人,从源点连 $1$ , 反之从汇点连 $1$。

求出最小割即为答案。评测记录(久远)

• P3227 [HNOI2013]切糕

  鉴于题目很不好懂,特别解释一下题意 :

  有一个 $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$ ,则无影响。

按照上述方法建图后求最小割即可。 评测记录

• P6054 [RC-02] 开门大吉

不难发现一套题可以整体处理,首先计算出第 $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;

评测记录

• P5458 [BJOI2016]水晶

这是一张密铺图,虽然不能像方格图那样染成两色,但是能按照 $(x+y+z)\bmod 3$ 染成三色。

观察发现,共振总是恰好包含三种颜色的水晶各一个。要用最小的代价“割断”共振。

可以看做一个三层图,有若干个限制,每个分别选取每一层的一个点组成三元组 $(a,b,c)$ ,要求它们不能同时存在。

一般的情况不太可做,随手建了个模得了 $40'$ 结果调了一年发现是假的 : Link

观察限制的特殊性,发现能量源的地位十分特殊。

将两种共振综合考虑并讨论,能发现等价的约束 : 某个能量源若存在,其周围最多只能有一种颜色的点。

不妨称能量源为红色,另两种为黑白。则从源连向黑点,从白点连向汇,容量为点权。

接下来,对于一个红点,拆成出入点,中间连边,容量为点权。对于相邻的黑点,连边到入点,对于相邻的白点,从出点连向它们,边权均为 $\inf$。

不难发现,该图的割的条件和转化后的约束等价。

接下来就是最小割了。一些细节 :

• 点的位置可以用 $(x-z,y-z)$ 更好地描述,然后用std::map检索。
• 由于 $10\%$ 的存在,需要把容量整体乘以 $10$ 变为整数。

评测记录

• P3756 [CQOI2017]老C的方块

仍然是一道奇怪的题目。

发现四种形状都恰好包含一条蓝色竖线和四个格子,那么不妨把方格图染成四色,使得每个形状恰好含有四种颜色各一个。

经过一阵手玩之后,染成了这样:

有了上一题的教训,我们不拆分,综合考虑这些限制,发现等价于要求下列子图中,四种颜色不能同时存在。

那么我们按照右侧的方法建边,就能限制至少割掉一种颜色。

接下来就是大量染色和连边的细节,就不赘述了。

最后求最小割,由于图近似二分图, $10^5$ 也能过。[评测记录] ()

• 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 ),由于边非常多,可能需要卡常。 评测记录

• P1361 小M的作物

  题意 : 把若干个物品分配到$A,B$两个盒子里面。每个物品分到不同的盒子有不同的收益。

  同时,钦定若干个物品集合一并丢到某个盒子里面的额外收益。

用最大流的思路并不容易建模。注意到这里只有两个盒子,选某个盒子可以看做割另一个盒子。

首先建立一个不考虑集合的图。可以把每个点串联$A,B$的权值边,这样只会割掉其中一个。

不难想到$A$做源,$B$做汇,中间是物品,边为对应权值。

现在考虑集合,对于某个集合,如果其中某个点的$A$边被割掉,那么其集合$A$边也必然被割掉。

我们可以考虑把集合$A$边和其内的物品$A$边并联,这样一旦要割必然一起割掉。

这样,我们对每个集合建立$A$虚点,和源相连,边权为集合权值。

然后连边到对应的物品上,边权为INF防止被割。

如果要割掉任意一个物品边,都必须要割掉所对应的所有集合边,否则白割。

整张图是对称的,对 $B$ 集合的连边类似。

由于图很稠密,写vector会快一点(2倍速左右)

评测记录

• P4313 文理分科

棋盘和四连通是吓唬人的,根本不需要黑白染色,其实就是 P1361。评测记录

• P1646 [国家集训队]happiness

棋盘和四连通又是吓唬人的,其实就是 P1361。评测记录

• CF311E Biologist

其实就是 P1361,只不过多了个倒贴钱。评测记录

• P1935 [国家集训队]圈地计划

这是个四连通网格图,先黑白染色变成二分图。

不相同才有奖很不爽,直接交换右部点的 $A,B$ ,变成相同有奖。

然后就是P1646了。评测记录

• P3308 [SDOI2014]LIS

模仿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)$ 的,似乎不太行。由于问题的特殊性随便写一点剪枝就很快了。

评测记录

• CF724E Goods transportation

首先有一个显然的最大流解法 : $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)$。 评测记录

最大闭合子图建模

• P3410 拍照

  题意 : 有$n$个元素,要求选择若干个组成集合$S$,选择每个元素都有代价。

  给出若干个悬赏$T$,如果$T\subseteq S$则获得该悬赏的奖励,问最大净收益。

经典问题。元素必须集齐可以转化成闭合子图条件。

每个悬赏点权为奖励,出边连向所需的所有元素。这样,由于图闭合,想获得奖励,所有这些元素都必选。

元素的点权为(负)自己的代价。跑最大闭合子图模板即可。

评测记录

希望构造方案请见 P2762 太空飞行计划问题

• P2805 [NOI2009]植物大战僵尸

  发现不会做这道题是写作本文的动力之一。

  题意 : 一个网格图上,有若干个法阵,每个都有其防御位置集合。

  我们可以从地图右侧发射光球,向左飞行。如果光球途径某个(未摧毁)法阵的防御范围,则会被吸收而不能起到攻击作用。

  对于一个法阵,如果其能源参数为负数,则表示摧毁这个法阵需要付出能源,否则表示能收益能源。

  问在这次攻击行动中,能获得多少能源的净收益?

而要想摧毁一个法阵,必须要把防御它的其他法阵都干掉,则对应“出边必选”的闭合条件。

由于光球只能向左飞行,摧毁一个法阵需要摧毁之前的所有法阵,可以认为每个法阵会保护身后的一个。

我们将每个法阵向防御它的所有法阵连边,然后求最大闭合子图即可。

问题在于可能有一些法阵互相保护,这些法阵就相当于无敌了(和经典的最大权闭合子图不同),被它们保护的其他法阵也无敌了。

可以在反图上拓扑排序取出没有无敌效果的点。

评测记录

• AT3672 [ARC085C] MUL

能够发现, 若打碎第 $k$ 个水晶,则必须打碎编号为 $k$ 的倍数的水晶。(这类约束很可能是个DAG,排个序看看就得到了)

然后我们可以从 $k$ 向着 $2k,3k,4k...$ 连边( 共 $O(n\log n)$ 条 ),这样打碎的水晶就是闭合子图,求最小权闭合子图即可。

注意需要开long long。 评测记录

• P4174 [NOI2006]最大获利

某个用户能贡献当且仅当其使用的两个基站都建造,最大闭合子图模板题。评测记录

• CF1082G Petya and Graph

选某条边一定要选两个端点,变成 P4174。评测记录

• P3973 [TJOI2015]线性代数

首先把式子化一化 : (不熟悉线性代数是不是就跪了啊……)

$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]$

为了避免小数,把流量扩大一倍,求最小割即可。

评测记录

前面的几个题也都可以如此减少点数到 $O(n)$ 级别 ( 而非 $O(m)$ )。

• P3749 [六省联考2017]寿司餐厅

首先能够发现,由于可以取多次,每次只取一个区间的限制可以忽略。

观察代价计算方式,每种代号的寿司,只要吃任意一种,都会带来 $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$)连边。

求最大权闭合子图即可。评测记录

• P3872 [TJOI2010]电影迷

一种扩展的最大闭合子图。原先是要求一定闭合,现在可以花费某种代价删去一条有向边的约束。

仍然考虑类似的建图,正权点连源,负权点连汇,有向边的边权不再是 $\inf$ 而是割掉的代价。

答案仍然是正点权和减去最小割。评测记录

• P4177 [CEOI2008]order

若不存在租用,完成一项工作必须购买对应的所有机器,这就是个经典的最大闭合子图问题。

接着考虑租用,可以类似上一题,将租用视作花费一定代价忽略某条边的闭合限制。

即 : 从每个工作向对应的机器连边,边权为租用费用。然后求解扩展最大闭合子图。

评测记录

• CF103E Buying Sets

容易发现,题目中给出的特殊性质就是 $\rm Hall$ 定理。

所以我们建立二分图,左侧是集合,右侧是元素,集合向其中的元素连边,一定有完美匹配。

任取一种完美匹配,不妨设集合 $i$ 匹配到了元素 $p_i$。

我们取 $k$ 个集合的匹配元素集合,就能得到这 $k$ 个集合的并集的一个子集。

若子集等于并集,这就是一个合法解,若并集更大则不合法。考虑如何限制,不难想到利用闭合子图。

让集合向着所包含的元素连边(强制选并集),元素沿着完美匹配向着集合连边,求最小权闭合子图即可。

评测记录

• P5295 [北京省选集训2019]图的难题 & B. 【UR #11】元旦老人与丛林

首先可以手玩一下,能够发现一个图合法的必要条件 : $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 [国家集训队]部落战争

观察到只能向下移动,这是个 DAG ,然后求解(点不相交)的最小路径覆盖即可。

评测记录

• P5769 [JSOI2016]飞机调度

发现按时间分层点数太多无法承受,注意到任务数量较少,而且都以绝对时间标定,不妨将任务看成状态。

先使用 Folyd (注意维修时间)求出两两最短路,然后将每个任务连向完成后(注意必须直飞)还来得及接的其余任务。

按起飞时间排序,我们能发现这是个DAG,跑最小路径覆盖即可。

评测记录

• P4589 [TJOI2018]智力竞赛

考虑二分,每次判定能否答完价值低于 $mid$ 的问题。

问题转化成 : 给出一个DAG,使用允许相交的 $n+1$ 条链进行覆盖,能否把关键点全部盖住。

搞个传递闭包就转化成可相交链覆盖了。

由于点数较少,也可以直接枚举并加边。评测记录

• CF590E Birthday

首先能够发现,包含关系是一个偏序集。

建立AC自动机,众所周知,fail树中,祖先是儿子的子串。

暴力跳fail连边复杂度是$O(n*len)$的,不可取。(听说dfs遍历fail树会爆栈)

一个比较好的方法是,每个点向最近的一个祖先连边,然后传递闭包。

然后就变成了最长反链问题,复杂度为$O(n^3+len)$。评测记录

二分图建模

比较平凡的二分图匹配除外。

• P3355 骑士共存问题

能够发现影响是二分图。(国际象棋中,骑士走一步,落脚点和起点的颜色一定不同)

然后求解二分图最大独立集。

评测记录

• P3033 [USACO11NOV]Cow Steeplechase G

容易发现横线段互不相交,竖线段互不相交,这是个二分图。

选出互不相交的尽量多的线段,等价于二分图最大独立集。

评测记录

• P2423 [HEOI2012]朋友圈

题意就是让我们求解朋友关系的最大团。在一般图中,这是个NP问题,我们需要利用本题中图的特殊性质。

观察 $A$ 中的人, 发现朋友关系是和最后一位有关的二分图,这样,我们在 $A$ 中只有可能选择 $0,1,2$ 个人,可以暴力枚举。

观察 $B$ 中的人, 可以发现补图也是个二分图。由于原图的最大团等于补图的最大独立集,求解二分图最大独立集即可。

出题人比较憨逼,给这么大的数据范围,然而造得很水,我们可以随手加几个剪枝用Dinic跑过去……

评测记录

• CF976F Minimal k-covering

发现没见过类似的模型,直接做比较困难。

不妨对答案方案取补,限制就变成了 : 每个点最多被连接 $d_i-k$ 次。

我们求出(带容量的)最大匹配,然后取补就能得到最小的 $\rm k-match$ 集。

对每个 $k$ 重新建图效率低下,能够发现 $k$ 减小 $1$ 之后,相当于图中的某些边容量集体增大 $1$ ,在残量网络上增广即可更快地计算。

评测记录

• CF1198E Rectangle Painting 2

注意到代价是$\min$,肯定每次涂一整行或者一整列最优。

现在问题就是,对于每个黑点,要么所在的行被涂黑,要么所在的列被涂黑。

这能够转化成二分图最大点覆盖问题 : 行在左边,列在右边,黑点是中间的边。

但是正方形网格非常大,黑色矩形却很少。

考虑暴力离散化得到 $O(m^2)$ 个矩形,然后就是个带容量的二分图最小点覆盖了(等于最大流)。

评测记录

• CF786E ALT

将居民和守卫看做二分图,居民对守卫的要求看做边。不难发现这个二分图的最小点覆盖就是答案。

显然 $O(n^2)$ 条边是无法承受的,考虑优化建边,由于这是树,考虑树剖。点数 $O(n)$ ,边数 $O(n\log^2n)$ 。

构造方案需要按照割集查看,不能直接利用二分图的性质了。

评测记录

• P4055 [JSOI2009]游戏

这是个方格图,首先黑白染色变成二分图。

现在就把问题抽象成了一个二分图博弈 : 可以自行选取起点,通过二分图上的边移动,并将该边删去,不能移动者负。

先求出一个最大匹配,假设先手选在某个非匹配点开始。

那么,若没有出边,则后手负。若有出边,则后手必定来到匹配点,否则可以增广。

接着,先手可以走匹配边,这样又变成了后手到达非匹配点的局面。

若有出边则后手必定来到匹配点,否则产生交错路,可以增广。

先手总是可以走匹配边,后手必败。

而最大匹配可能有多种,某个点只需要在其中任意一种不是匹配点,先手都有必胜策略。

接着说明其他的点都是先手必败。这些点必然总是匹配点,那么后手操作一次之后就总是变成先手到达非匹配点的局面,先手必败。

所以我们求出所有可能的非匹配点,即为答案。

大多数人都是用的匈牙利,所以判断非匹配点在二分图上dfs一下偶路径就好了。

网络流也不是不能做,枚举每条满流边,把流量退掉,查看是否存在新的增广路。这可以搜索出 $S,T$ 集之后$O(m)$快速求出。

总复杂度就是 $O(E\sqrt{V})=O(n^3)$ 。 评测记录

Hall定理

• P3488 [POI2009]LYZ-Ice Skates

可以二分图匹配做,但是数据范围太大,观察到只需要判定是否有完美匹配,考虑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$ 即可。

评测记录

• CF981F Round Marriage

考虑二分,然后转化成了判定二分图是否有完美匹配。

先拆环为链,距离不超过环长的一半,这是合法的。

和上一题中类似,选择连续的 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

对于 $A$ 的每个长度为 $m$ 的子区间判断是否和 $B$ 有完美匹配。

将 $B$ 降序排序。能够发现, $A$ 中的一个元素能够匹配的 $B$ 元素一定是一个前缀。

类似地,选择 $A$ 中升序排序之后的前缀 ,能够使得连向 $B$ 的点集尽量小。

对两个序列前缀的限制可以等价为 : $B_i$ 至少要被匹配 ${m-i+1}$ 次。

先离散化,每个 $A$ 所新增的匹配次数是一个区间加,依次处理区间,每次移动相当于一次增加和一次删除。

事先将 $B_i$ 置为 $-(m-i+1)$ ,然后线段树维护最小值,看看是否 $\geq 0$ 即可。

评测记录

• CF1009G Allowed Letters

可以按照字典序贪心,但是可能导致后面没东西填,产生后效性。

填写每一位之前,可以先判断一下后面的位能否形成完美匹配,如果能才填写。

具体的讲,每个字母按照数量限制流量,右边连向每个位置,跑二分图带容量匹配看看是否满流即可。

但是这会需要 $O(n\Sigma)$ 次二分图匹配,显然无法承受。考虑到我们只需要判断是否形成完美匹配,可以使用扩展霍尔定理。

又能发现字符串上的一个位置最多只有 $O(2^\Sigma)$ 种限制,可以把限制相同的点直接压起来。

观察填写一个位置可能造成的影响 : 一个右侧点和一个左侧点容量一并减少 $1$。

那么,可以每次填写后 $O(2^\Sigma)$ 暴力枚举左侧的点集,能够发现右侧的邻域就是 : 全集减去补集的子集求和。

暴力维护一下子集求和就可以$O(1)$判定了。总复杂度是$O(n2^{\Sigma})$。

评测记录

• AT2645 [ARC076D] Exhausted?

  [??记录]AT2645 [ARC076D] Exhausted?

• CFgym102268D Dates

暂咕。

最小割树

• P3329 [ZJOI2011]最小割

建立最小割树,枚举源点暴力 dfs 求每两个点之间的最小割即可。评测记录

• UVA11594 All Pairs Maximum Flow

做法同上,注意行末不能有空格。评测记录

• P4123 [CQOI2016]不同的最小割

把最小割树的边权丢进 std::set 然后输出 size() 即可。评测记录

• P3729 曼哈顿计划EX

安全系数其实就是最小割。一个点集的最小割等于其中任意两点的最小割的 $\min$ ,也就等于最小割树中点集内部的最小边权。

建立最小割树,问题变为 : 选择一个点集,在满足权值和 $\geq k$ 的前提下,点集内部的最小边尽量大。

这可以把最小割树中的边按权值从大到小依次加入,使用并查集维护最大的联通块权值和。离线从小到大回答询问。

评测记录

• CF343E Pumping Stations

建立最小割树,相当于在树上按一个排列移动,求路径$\min$的和的最大值。(这就开始和最小割无关了)

考虑限制最紧的一条边 : 权值最小的那条边。

我们要尽量少地经过这条边,至少经过一次,也容易构造出这个下界。

然后,我们这条边删去,得到两颗子树,变为子问题。

合并时将两棵子树的排列直接接在一起即可,接口上恰好经过一次权值最小的边。

这部分复杂度$O(n^2)$。 评测记录

2.费用流题目泛做

可能会用 $(u,v,f,c)$ 表示一条从 $u$ 到 $v$ 的,容量为 $f$ ,费用为 $c$ 的边。

类最短(长)路问题

• P2153 [SDOI2009]晨跑

注意到点不相交的限制,拆点并限制流量为$1$。原图中的边不限流量,费用为边权。

评测记录(久远)

• P2045 方格取数加强版

没有点不相交的限制,但是每个点只能贡献一次。

把每个点拆成出入点,之间有两条边,一条只能走一次,但是能贡献费用,另一条可以走无穷多次,但是费用为$0$。

原图的边不限流量,无费用。

然后跑最大费用最大流即可。(增广路较长,费用范围大,图稀疏,不使用zkw的一例)

评测记录(久远)

• P4013 数字梯形问题

拆点,之间的边费用为点权。

• 限制① : 点限制流量为$1$,边限制流量为$1$

• 限制② : 点不限流量,边限制流量为$1$

• 限制③ : 点和边均不限制流量。

评测记录

• P3356 火星探险问题

我们将每个位置拆成出入点,先连上INF边,若有石块,额外连一条容量费用均为$1$的边。

容易发现这是个DAG,原图的边不限流量。求最大费用最大流即可。

主要难点在于输出方案,通过比对原图和残量网络能够得到每条边被多少辆车子经过。

评测记录

• P4012 深海机器人问题

和上一题差不多,只不过贡献在边上,而且变成了多源多汇。(甚至不需要输出方案)

评测记录

• CF818G Four Melodies

我们考虑让一个流代表一个子序列,那么流只能从左往右,这是个DAG。

要长度总和尽量大且不交,非常套路地把每个位置拆点,限制容量为 $1$ 费用为 $1$。

直接按照题目中给出的限制向后连边,可能会产生 $O(n^2)$ 条边,无法承受。

能够发现,对于模 $7$ 的限制,我们,然后使用传递性即可。这需要建立$\inf$边来表示经过但不选取。

对于 $±1$ 的限制,能够发现满足条件的集合模 $7$ 也是同余的,那么只需要连接后面最靠近的点。

求最大费用最大流即可。评测记录

• UVA1486 Transportation

考虑差分建边,也就是给每条边的每单位流量单独建边,容量为 $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$$

由于平方的凸性,最小费用流一定会先走代表流量低的边,这就保证了合法性。

由于容量很小,直接建就好了。接着就是最小费用最大流的模板了。

评测记录

• CF1187G Gang Up

来了个真正的按时间分层费用流。考虑一条链的最差情况,容易证明时间消耗最多 $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$ 的代价。

接下来就是最小费用最大流。评测记录 (以接近$9$倍效率优势拿到了最优解)

• P4066 [SHOI2003]吃豆豆

观察吃豆人不能相交的限制,其实可以相交了就交换路线,直接无视这条限制。

但是每颗豆子只能吃一次的限制仍然存在,我们拆点限制容量即可。

一条边容量为 $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]交换棋子

由于棋子只有两种颜色,可以让所有黑色棋子归位,这样白色棋子自然就也放好了。

考虑一个黑色棋子移动的影响 : 两个方格的移动次数减一。

考虑一条路径,头和尾的移动次数减一,中间的移动次数减二。

我们“只出”,“只入”和“出入”三种走法对一个格子的影响(以及费用)是不同的。

可以把点拆成三个 : $left,mid,right$

连 $left\rightarrow mid\rightarrow right$ ,边权为 $\lfloor w/2\rfloor$

这样,一个点完整地从 $left$ 走到 $right$ 会经过两条边,而从 $left$ 到 $mid$ 或者从 $mid$ 到 $right$ 只需要一条边。

需要求解最小交换次数,可以给每条边附加 $1$ 的费用。

还有个问题,如果某个点原来有黑棋,后来没有,或者原来没有后来有,必然产生一次“只入”或“只出”。

如果 $w$ 是奇数,我们把对应的边流量$+1$ 即可(补偿整除损失)

然后源点向原来的黑棋 $mid$ 连边,后来的黑棋 $mid$ 向汇点连边。

各个位置之间按八联通规则连边,跑最小费用最大流即可。

评测记录

• P4452 [国家集训队]航班安排

观察数据性质,已经给出了满足三角不等式的费用和时间矩阵,也就是说我们直飞一定是最优的。

容易想到根据时间分层,但是点数太多效率低下。

观察到请求数量不多,且都由绝对时间限制,这就说明两个请求之间的关系是确定的。

我们给每个请求建立一个点,容量为$1$,点权为净收益。

然后查看所有其他请求是否来得及接,如果来得及,连边费用为 $-$花费。

注意也要与基地连边。

求最大费用最大流即可。评测记录

费用匹配

• P4014 分配问题

这是个经典的带权二分图匹配问题,在中间的匹配边上加上费用,最大费用最大流即可。

由于图较为稠密,且增广路一般较短,建议试试zkw费用流。

评测记录

• P3967 [TJOI2014]匹配

多了一问 : 二分图带权匹配的必须边。

懒得分析,由于数据范围小,可以搞一些比较暴力的解法。

直接暴力枚举所有目前在匹配中的边,删去查看带权匹配是否减小。这样需要 $O(n)$ 次匹配。

原来还搞了个 $O(n\log n)$ 次的分治,思维江化了…… 评测记录

• P4015 运输问题

加入了流量,带权多重二分图匹配。 评测记录

• P3705 [SDOI2017]新生舞会

先搞个01分数规划,将边的权值置为 $a-mid*b$ ,现在就是要判定是否存在匹配的权值总和 $\geq0$。

然后就是带权二分图匹配,跑(实数)最大费用最大流即可。

如果觉得太慢可以转成整数费用流,学习zkw,或者学习更加有理有据的带权匹配算法。

评测记录(EK) $\$ 评测记录(zkw)

• P4134 [BJOI2012]连连看

能够发现就是个带权匹配,没听说过2012年引入了一般图带权匹配,先有理有据地猜测这是个二分图。

建立出 $[1,1000]$ 的图,染个色,发现确实是二分图。然而听说 $[1,10^4]$(或者更大) 的图就不是了……出题人你想干啥?

然后跑个二分图带权匹配就是了,注意到$(x,y)$匹配的收益是$x+y$,甚至可以直接把费用设在源汇边上。

评测记录

• P2488 [SDOI2011]工作安排

仍然是二分图带权带容量匹配,只不过费用是分段函数。

观察数据限制发现,这个分段函数是凸的,那么直接给每一段建立一条边,一定会先走前面的边,就已经符合题意了。

求最小费用最大流即可,注意答案存储需要开long long。 评测记录

• UVA11613 Acme Corporation

如果没有保质期限制,非常简单。

对每一天建点,连源,容量为生产力,费用为(负的)成本; 连汇,容量为最大售出量,费用为单价。

每天连向下一天,费用为 $I$ 容量为 $\inf$ 。

但是本题有保质期限制,所以第 $i$ 天生产的商品不一定能出售给后面的所有时间。

数据范围较小,可以直接转为费用匹配。

对每天分别建立出点入点。分别计算出从第 $i$ 天售给第 $j$ 天的单位收益然后连边,这就方便处理保质期的限制了。

我们要求的不一定是最大流,而是最大费用任意流,所以当费用为负时直接退出即可。

评测记录

• P2053 [SCOI2007]修车

某辆车先修理这一决策,不仅仅会导致这辆车花费等待时间,还会影响到排在后面的车。

我们考虑提前计算贡献。对于某个技术人员,排名倒数第 $i$ 的车会让之后(包括自己)的 $i$ 辆车花费 $t$ 的时间等待。

这能够让我们简化状态 : 某辆车,在某个技术人员手中,排名倒数第几。对应的贡献就是确定的。

现在就变成了一个带费用的匹配问题,跑最小费用最大流即可。点数是$O(nm)$,边数是$O(n^2m)$的。

评测记录(久远)

• P2050 [NOI2012]美食节

和上一题是本质相同的,难点在于数据范围增大了,不能直接跑费用流。

容易发现,如果倒数第 $i+1$ 的匹配位置没有被占用,那么倒数第 $i$ 的位置绝对不会被占用。

EK算法每次只会找到一条增广路,我们可以每次增广之后,查看新的匹配,然后把下一个空加入即可。

这样,总点数就是$O(n+m+p)$的,边数也就是$O(n(n+m+p))$。

图比较稠密,推荐使用vector。评测记录

• CF863F Almost Permutation

首先,容易把所有的限制转成某个位置的值 $\in[l_i,r_i]$ 的形式。

然后注意到值域不大,我们可以对每个位置的每种决策(匹配)分别建边。

每个点有$1$的流量,出边连向 $[l_i,r_i]$ 中的各个计数桶。

对于每个桶,代价并不是线性的。这也好办,类似上一题枚举代价差分即可,由于平方是凸函数,一定会先走前面的边。

求最小费用最大流即可。评测记录

本身就有 $O(n^2)$ 条边,无需额外的单调性动态建边优化。若使用区间数据结构则可能需要。

• P4307 [JSOI2009]球队收益 / 球队预算

每场比赛设置一个点,流量限制为 $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)$ 级别,就无需单调性加边优化了。

评测记录

• P4249 [WC2007]剪刀石头布 & CF1264E Beautiful League

题意 : 给一个部分确定的竞赛图定向,要求三元环尽量多。

我们不妨最小化非三元环子图,然后用三点子图 $\binom{n}{3}$ 去减。由于其不对称,可能特征更明显,便于统计。

考虑某三点子图不是三元环的情况(请自行画图) : 某个点入度为 $2$ ,某个点出度为 $2$ , 某个点出入都是 $1$。

来到整张图中考虑,能够发现某点若入度为 $k$ ,则能选择出 $\binom{k}{2}$ 个此类子图,而且每个子图只会在入度为 $2$ 的点处计数,不会重复。

对于每条未定向的边,限制流量为$1$,这个流量(入度)可以分到任意一个端点去。

对于每个端点,连向汇。此时的费用不是线性的,由于 $\binom{k}{2}$ 是凸函数所以可以差分。

评测记录1 & 评测记录2

• P6061 [加油武汉]疫情调查

图的最小环覆盖?

先跑一个Folyd。

按照套路把点拆成出入点,某两个点之间的匹配可以看做将两条路径接在一起。

进一步发现,对于一个完美匹配(置换?),按照匹配连接路径之后正好得到若干个环。

那么我们在这个二分图的 $(u,v)$ 之间连边 $dis[u][v]$ ,在 $(u,u)$ 之间连边 $a[u]$ 即可。

这样需要 $O(n^2)$ 条边,有点虚。但是,观察到 $m$ 不大,不妨直接把原图建出来代替这些 $dis$。

但是每个点自己成环,代价(距离)不是 $0$ ,考虑拆成出入点。

源连出点,入点连汇,从入到出免费不限流量,从出点到入点(反向)需要 $a[u]$ 的代价。

评测记录

• UVA12092 Paint the Roads

  题意 : $n$ 个点 $m$ 条带权边的有向图,要给边染色。

  让染色的边形成若干个回路,且每个点都恰好属于其中$k$个回路。问最少的染色边权和。

上一题的扩展,直接令每个点的出入度都为 $k$ 即可。

还需要限制每条边只能染一次,这就只能建立原图并拆点了。

评测记录 (数据似乎较弱……)

• CF277E Binary Tree on Plane

容易发现可能的父子关系是一个DAG,这就不会出现环。

观察到二叉树的每个点都必选,这就没必要限制流的连续性。(也就躲过了“分流”的难题)

将每个点拆成出入点,入点连汇,容量为$1$,表示必须存在于树中。

源连出点,容量为$2$,表示可以分$2$叉。

各个点之间连边,按照欧氏距离确定费用。

最后求解(实数)最小费用最大流。评测记录

• P4068 [SDOI2016]数字配对

奇怪的题目……要求费用为正?先考虑经典的费用流。

设 $c[i]$ 为第 $i$ 个数的素因子次数和,那么 $(x,y)$ 能配对,当且仅当 $a[x]|a[y]$ 且 $c[x]-c[y]=1$

由于能匹配的对子 $c$ 都恰好差 $1$ ,能够发现这是个二分图带权带容量匹配问题。

现在有要求费用为正的情况下流量尽量大,由于经典最大费用流算法中,每次按照最长路增广,最长路会逐渐变短。

这是具有单调性的,我们只需要使劲增广直到总费用为负数即可。注意最后一次增广可能只能获得一部分流量。

评测记录

• UVA1411 Ants

注意有多组数据,不要像我一样白WA两发。

注意到不同的方案中,关于相交的限制是不同的,多个可能的匹配之间的互斥关系十分复杂。

考虑先使用几何知识分析,若有两条相交的线段(灰色),将其调整成不相交的连接方式(黑色),长度一定会变短。

(可以使用三角形两边之和大于第三边证明)

所以,不难得到结论 : 对于一个交错的方案,必定存在一个不交错的方案,连线总长度更短。

由于题目保证有解,我们求解最小费用匹配就得到了答案。

评测记录

• P5331 [SNOI2019]通信

不难发现这是个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]循环格

不难发现这张图每个点只有一个出度,就是一个基环内向树森林。若满足“循环”的定义,一定是由若干个环组成。

“环森林”的充要条件就是 : 每个点都只有一个入度,一个出度,这可以视作匹配。

首先拆成出入点,各有 $1$ 的容量。

对于一个点,可以向四个方向(注意边界循环)匹配,若恰好是自己的初始方向,费用为 $0$ 否则费用为$1$。

然后就是二分图带权匹配了,由于费用小建议跑zkw。 评测记录

• 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$ 倍。 评测记录

不好归类的题目

• P2604 [ZJOI2010]网络扩容

第一问就是最大流。然后将源点的流量限制为 $\text{最大流}+k$

将每条边复制一份作为“扩容边”,容量为 $\inf$ ,费用为 $w$ ,求最小费用最大流即可。

评测记录(久远)

• P2517 [HAOI2010]订货

从第 $i$ 天连向汇,容量为 $U[i]$ ,表示卖出。

从源连第 $i$ 天,容量为 $\inf$ ,费用为 $D[i]$ ,表示购入。

从第 $i$ 天连向第 $i+1$ 天,容量为 $S$ ,费用为 $m$ ,表示存储。

求最小费用最大流即可。 评测记录

奇怪的是 $n\leq 50$ ,甚至有DP解法……建议加强到 $n\leq 10^3,S\leq 10^6$

• P3358 最长k可重区间集问题 & CF164C Machine Programming

很像朴素的匹配问题 : 每段只能匹配 $k$ 个区间。

我们向每个区间连边,问题来了,对于一段区间我们不好限制必须要整体选择。

一个关键的性质是 : 可以把最优解划分成选择若干次不交的区间集合的形式。能够发现选择 $k$ 次的最优方案就是答案。

考虑每个区间拆成出入点,之间容量为 $1$ ,费用为 $len$。

按左端点排序,每个区间向着后面不交的区间连边,容量为$\inf$,费用为 $0$ 。然而可能产生 $O(n^2)$ 条边。

注意到“不交”具有单调性,我们给每个区间入点到下一个入点之间新增一条边,容量为 $\inf$ ,费用为 $0$ ,表示经过但不选择。

这样就只需要向着后面第一个不交的区间连边了,边数降为 $O(n)$。

容易发现,一个流的意义就是选择一个不交的区间集合。

然后每个区间的入点都连源,容量为$1$,出点连汇,容量为$1$,表示可以任意开始结束。源汇的容量均为$k$。

求最大费用最大流即可。

评测记录1 & 评测记录2

• P3357 最长k可重线段集问题

和上一题就两个区别 : 长度的计算方式变了。有可能出现垂直于 $x$ 轴的线段。

我们将所有的位置 $*3$ 然后略微移动左右端点来模拟开区间即可。(注意垂直于$x$轴的情况)

评测记录

• P3980 [NOI2008]志愿者招募

神仙题.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]$ 的边一起扩大。

然后跑一个最小费用最大流即可。评测记录

有另一种更加循规蹈矩的方法,通过线性规划推式子转费用流。

设 $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$。

然后就是最小费用最大(可行)流。由于未知的原因,比上一种方法明显低效。评测记录

• CF802C Heidi and Library (hard)

神仙题.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}$ 合并。

观察这个模型,若某本书当天没有被扔掉,一定会一直待在书架里占用位置,直到被卖掉。

求最小费用最大流。 评测记录

我们巧妙地在回收站包含了信息,而利用题目中的要求必须满足的性质将状态缩减,把不同的书当做同样的流量处理。

类似的题 : CF132E Bits of merry old England & [评测记录] ()

输出方案的话,记录下每个售出和购入,将能串的串在一起,然后按时间顺序扫描即可。

3.上下界网络流题目泛做

可能会用 $(u,v,[l,r])$ 表示一条从 $u$ 到 $v$ 的,容量在 $[l,r]$ 之间的边。

用 $(u,v,[l,r],c)$ 表示一条从 $u$ 到 $v$ 的,容量在 $[l,r]$ 之间,费用为 $c$ 的边。

• P5192 Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流

考虑对每天分别拆点,流量限制为 $D$ ,向右侧连流量限制为 $[L,R]$ 边, 右侧点限制为$[G,\inf]$。

然后跑有源汇上下界最大流即可。评测记录

• P4843 清理雪道

观察“每条雪道至少被清理一次”的要求,相当于流量至少为 $1$ 。建立 DAG 并将限制设为 $[1,\inf]$ 即可。

接下来就是有源汇上下界最小流。

评测记录

• P2304 [NOI2015]小园丁与老司机

第一问考虑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]支线剧情

有源汇上下界最小费用可行流。

每条边至少被经过一次,流量限制就是 $[1,\inf]$。

然后把有源汇上下界可行流套上费用流就做完了。(注意要计算初始流的费用)

评测记录

• P4553 80人环游世界

容易发现只是在P4043的基础上把点的容量限制定死了。

评测记录

• P2469 [SDOI2010]星际竞速

由于引力大小的限制,若只考虑高速航行,这图是个DAG。

能够发现,空间跳跃的花费和起点无关,我们可以将方案等效抽象成以从起点跳跃开头的若干条路径。

于是就可以转化为和上面类似的DAG遍历问题。

求最小费用可行流。 评测记录

由于限制点不相交,还能转化成最小代价路径覆盖。

首先让每个点自成一条路径,此时代价是 $\sum A$。

仿照最小路径覆盖,建立二分图,一条匹配边就代表将两条路径合在一起。

所以从 $u\rightarrow v$ 建立一条 $\text{原边权}-A[v]$ 的边,表示合并之后代价的变化量。

但此时我们求的并不是最小费用最大流,而是最小费用合法流。

由于费用流中最短路一定会逐渐变长,我们只需要增广直到最短路为正即可。

比起上一种方法,不需要上下界,代码更短,跑得也要略快一些。评测记录

• P4542 [ZJOI2011]营救皮卡丘

去日本旅游的黑猫警长xswl

反正所有的据点最终一定会被干掉,多条路径之间,我们不需要关心相对顺序。

只需要限制每条单独的(摧毁)路径必须按顺序进行,最后把各个路径归并一下即可。

问题在于,目前占领了多少据点,可能影响到我们走的最短路。

先使用 Folyd 预处理出 $dis[u][v]=$ 只经过 $\leq v$ 的点,从 $u$ 到达 $v$ 的最短路。

如果一个人上一次摧毁 $x$ ,下一次摧毁 $y$ ,那么说明 $\leq y$ 的据点已经可以任意经过,最短路是$dis[x][y]$。

然后就是一个DAG的最短 $k$ 路径覆盖问题,类似于上一题。

同样也可以使用费用匹配求解路径覆盖。这里 $1$可以接 $k$ 条路径,所以容量是 $k$ ,其他点的容量(出度限制)都是 $1$。

评测记录

• P4311 士兵占领

直接建立矩阵对应的结构不好做,考虑从行“剥离”总和贡献到列。

给每行每列都建立一个点,有容量下界限制。

$S\rightarrow$行, 列$\rightarrow T$ ,中间无障碍的地方在对应行列之间连边 $[0,1]$ 即可。

然后是一个有源汇上下界最小流。

评测记录

• P4194 矩阵

题面用人话说就是 : 给出矩阵 $A$ ,要求构造同样大小的,元素都在 $[L,R]$ 内的矩阵 $B$ 。

使得矩阵 $C=A-B$ 每行的和以及每列的和的 $\max$ 最小。

考虑二分答案。绝对值的限制可以转化为 : 每行每列的和在 $[-K,K]$ 内。

减去已经确定的 $A$ 的贡献,就能得到 $B$ 每行每列的和的范围。

给每行每列都建立一个点,并如上所述限制流量。

直接建立矩阵的对应结构并不好处理,考虑从行“剥离”总和贡献到列。(类似P4311)

$S\rightarrow$行, 列$\rightarrow T$ , 然后每行每列之间连边 $[L,R]$ 即可。

跑有源汇上下界可行流来判定。注意会有负数流量,但是会被自动处理掉。

评测记录

• P1251 餐巾计划问题

个人认为是网络流24题中最好的前三道。

把每天拆成三个点 : 上午,下午(新),下午(旧)

从 $S$ 连到每天上午,容量为 $\inf$ ,费用为 $p$ , 表示购买餐巾。

从 上午 到 下午(旧) 连边,限制容量恰好为 $a$ ,费用为 $0$ ,表示需要用掉这么多餐巾。

从 上午 到 下午(新) 连边,容量 $\inf$ ,表示没用完的餐巾可以存储。

每天都有快洗部和慢洗部,分别向 $n$ 或 $m$ 天后的上午连边,容量 $\inf$ ,费用为 $f$ 或 $s$。

从 下午(旧) 分别连边到 $T$(表示丢弃) ,快洗部,慢洗部,,容量均为 $\inf$ ,费用为 $0$ 。(容易发现最优方案中不存在延期送洗)

不难发现 下午(旧)/快洗部/慢洗部 三个点可以合并, 上午/下午(新) 两个点可以合并。

求最小费用可行流即可。由于费用只有两种,写个多路增广即可有理有据地获得大幅效率提升。

评测记录(普通) & 评测记录(多路增广)

• CF1288F Red-Blue Graph

我们可以把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)$

然后求最小费用可行流,费用只有两种,多路增广会快。 评测记录

• CF708D Incorrect Flow

对于原图的边 $(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$。

求上下界最小费用可行流即可。

评测记录

• CF704D Captain America

不妨设 $r>b$ ,现在我们的目标就是让尽量多的盾牌染成蓝色。

考虑给每行每列分别建立点,一个 $(i,j)$ 的染色操作就相当于给第 $i$ 行和第 $j$ 列各增加 $1$ 单位流量。

绝对值的限制可以视作上下界,跑上下界最大流即可。

出题人有点猛,直接搞了 $10^5$ ,可能需要卡常数。

评测记录

• UVA1104 芯片难题 Chips Challenge

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)$ ,这就很稳了。

提交记录

还有一种不需要神仙模板的人类智慧做法。

注意到我们如果仅仅把放置当做流量,“能否放置”和“行列等量”很难兼顾。

不妨把放置和不放置都记作流量,然后给放置附上费用引导决策。

行列分别建点,形成二分图。源连行,列连汇,容量 $n$。

第 $i$ 行连第 $j$ 列,容量为所枚举的限制 $lim$ ,费用为 $1$。表示放置的个数,由于直接连边,自然满足行列等量。

对于可决策的区域 $(i,j)$ , 从行 $i$ 连到列 $j$ ,容量为 $1$ ,费用为 $0$ ,表示不放置。

对于必须不放置的区域 $(i,j)$ , 从行 $i$ 连到列 $j$ 。

接下来可以选择使用上下界,限定流量恰好为 $1$,可是你会发现新的图中有正环,还是得消环。

另外一种神奇的做法是 : 容量为 $1$ ,费用为一个大于 $n\times n$ 的数 $M$ ,这样就会绝对优先地走这些边。

如果满流,且所有 $M$ 边满流,且 $lim$ 自洽,则合法。

提交记录

随手一写居然两种做法都1A了,有点感动。

• UVA1659 帮助小罗拉 Help Little Laura

  题意 : 给定一个平面上的一些有向线段,涂色费用为 $dx-y$, 其中 $d$ 为边的长度(实数), $x,y$ 为给定参数。

  环路的涂色费用为各边涂色费用和。找出一些环路,使得这些环路边不相交,且涂色费用总和最大。

最大费用循环流的模板题。直接求解最大费用无源汇可行流会遇到正环,可以使用和“负环费用流”类似的方法。

也即 : 把原图的 $(u,v,cap,len)(len>0)$ 替换成 $(u,v,[cap,cap],len),(v,u,[0,cap],-len)$。

意思就是先把所有的正权边强制流满,然后建立反向边来退流。

接着就是上下界无源汇最小费用可行流,不难发现图中没有正环了。

这个题浮点数不开SPJ,手动加1e-7才能通过……

评测记录