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

command_block

2019-08-13 13:34:45

Personal

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

1.网络最大流题目泛做

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

最大流建模

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

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

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

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

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

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

评测记录

先用朴素DP求出 s。

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

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

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

评测记录(久远)

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

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

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

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

评测记录

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

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

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

难以通过精妙的建模规避掉这些问题。奇妙的是,直接将 b_1,b_2 交换,再次判定即可得到正确答案。

评测记录

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

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

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

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

评测记录

匹配问题

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

二分图的定义见第二节。

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

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

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

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

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

评测记录

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

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

评测记录(久远)

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

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

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

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

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

评测记录

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

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

评测记录(久远)

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

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

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

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

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

评测记录

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

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

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

评测记录

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

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

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

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

评测记录

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

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

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

评测记录(久远)

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

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

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

评测记录

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

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

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

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

评测记录

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

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

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

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

评测记录

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

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

评测记录(久远)

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

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

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

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

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

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

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

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

[评测记录] ()

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

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

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

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

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

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

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

评测记录

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

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

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

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

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

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

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

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

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

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

棋盘染色

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

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

最小割建模

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

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

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

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

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

评测记录(久远)

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

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

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

评测记录

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

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

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

评测记录

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

评测记录(久远)

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

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

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

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

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

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

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

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

我们把蛋糕下表面的点连上源,上表面的点连上汇,这就是一个最小割问题。

如何控制 f 值的差呢? 想办法让差超过 D 的方案连通即可。

我们可以从某个 z=u 的位置,向着四相邻竖轴 z=u-D 的位置连 \inf 边。

这样,如果两个相邻轴的 f 函数差大于 D , f 小的割挡不住 f 大的割的一个侧生边,无法构成最小割。

若两个相邻轴的 f 函数差不超过 D ,则无影响。

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

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

评测记录

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

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

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

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

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

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

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

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

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

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

评测记录

仍然是一道奇怪的题目。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

评测记录

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

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

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

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

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

然后就是P1646了。评测记录

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

评测记录

首先有一个显然的最大流解法 : 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 个点分类讨论 :

转移方程 : 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)。 评测记录

最大闭合子图建模

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

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

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

评测记录

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

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

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

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

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

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

评测记录

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

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

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

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

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

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

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),分类讨论:

在最小割中,如果想要仅用 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}

上面是两个点的情况,现在考虑多个点的情况。

根据题意,$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) )。

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

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

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

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

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

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

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

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

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

评测记录

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

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

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

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

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

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

评测记录

首先可以手玩一下,能够发现一个图合法的必要条件 : 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(偏序集)建模

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

评测记录

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

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

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

评测记录

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

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

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

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

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

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

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

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

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

二分图建模

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

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

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

评测记录

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

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

评测记录

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

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

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

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

评测记录

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

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

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

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

评测记录

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

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

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

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

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

评测记录

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

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

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

评测记录

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

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

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

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

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

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

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

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

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

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

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

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

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

Hall定理

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

评测记录

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

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

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

[评测记录] ()

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

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

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

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

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

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

评测记录

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

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

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

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

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

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

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

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

评测记录

暂咕。

最小割树

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

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

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

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

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

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

评测记录

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

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

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

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

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

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

2.费用流题目泛做

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

类最短(长)路问题

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

评测记录(久远)

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

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

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

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

评测记录(久远)

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

评测记录

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

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

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

评测记录

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

评测记录

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

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

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

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

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

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

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

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

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

评测记录

来了个真正的按时间分层费用流。考虑一条链的最差情况,容易证明时间消耗最多 n+k。点数就是 O(n(n+k)) 的。

原图的边有平方代价,可以差分一下变成多条边(都是套路)。直接建立所有的边,边数会达到 O(mk(n+k))≈5\times10^5 级别。

由于选择边的单调性可以动态建图(类似P2050),边数可降为 O\big((n+k)m+nk\big)≈2\times10^4 级别。

接下来就是最小费用最大流。[评测记录](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 向汇点连边。

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

评测记录

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

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

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

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

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

注意也要与基地连边。

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

费用匹配

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

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

评测记录

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

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

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

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

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

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

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

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

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

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

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

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

评测记录

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

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

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

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

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

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

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

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

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

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

评测记录

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

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

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

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

评测记录(久远)

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

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

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

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

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

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

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

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

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

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

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

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

评测记录

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

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

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

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

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

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

评测记录1 & 评测记录2

图的最小环覆盖?

先跑一个Folyd。

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

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

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

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

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

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

评测记录

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

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

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

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

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

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

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

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

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

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

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

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

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

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

评测记录

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

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

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

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

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

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

评测记录

不难发现这是个DAG,问题就是最小权路径覆盖。可以转为二分图带权匹配。

直接暴力建边,边数可能达到 O(n^2) ,无法通过。

观察到我们每次都在向一个编号前缀连边,而费用是绝对值,与 a 的相对大小有关,限制相当于二维偏序。

离散化之后主席树优化建边即可。具体来讲,需要维护两颗主席树,一棵点权为 -a_i ,另一颗为 +a_i。

连边时,向第一棵的 [1,a] 连边 +a ,向第二棵的 (a,\max a] 连边 -a。

这样边数就降为了O(n\log n) ,但是点数也变为了 O(n\log n) ,卡卡常就过了。

[评测记录] ()

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

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

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

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

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

非常有意思的题目。

不漏水的要求,相当于让相邻格子之间流量尽量大。

可以给棋盘染个色变成二分图,黑的位置连源,白的位置连汇,就能让相邻格子产生流。

考虑对这些形状分类讨论。设 (f,c) 为一条容量为 f ,费用为 c 的边。

由于每个点可能有四个接头,我们对每个位置建立 5 个点,分别为 “上下左右中”,其中“中”限制流量。

下面对于特定朝向的形状进行分析,只需要旋转就能得到所有情况。

注意需要根据“中”连的是源还是汇,来确定边的方向。

别忘了在相邻的对应方格的对应接头之间连上 (1,0) 边。

然后把讨论在代码里复现,求最小费用最大流。

由于费用很小,增广路较短,多路增广的zkw比EK快 20 倍。 评测记录

不好归类的题目

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

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

评测记录(久远)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

求最大费用最大流即可。

评测记录1 & 评测记录2

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

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

评测记录

神仙题.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

如果我们把每个式子看做一个点,正数表示流入,负数表示流出,等式就代表着流量平衡。我们能得到如下的建图方法。

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

神仙题.jpg

观察一本书的行为 : 若 j,i(j<i) 天都需要,如果一直持有该书,则只需要付一次钱,否则需要两次。

“持有”这一状态不包含流量的改变,不好建模。不妨考虑叠缩,视作可以在昨天售出上次供给的同类书,并且总会再次购入。

这样就使得我们的策略一定合法。

将每一天拆成 : 售卖处 r ,购书处 u ,和回收站 v 。以 (f,c) 表示容量为 f ,费用为 c 的一条边。

每天的顺序是: 先卖,再买,然后回收。

不难发现,可以将 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 的边。

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

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

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

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

评测记录

第一问考虑DP,注意到可能的路径并非DAG,需要仔细考虑。

能够发现有每个 y=c 上不超过 1000 个点限制,这指示我们采用按 y 分层的比较暴力的做法。

设 f(i,j) 为到达 y=i 的从上到下第 j 棵树许愿,之前能许愿的最多次数。

转移让前面的树贡献,每棵树只会有“上,右上,左上”三种转移方式。拿桶搞一搞就容易得出转移目标。

接下来是同行转移,我们可以非常暴力地枚举进入点和离开点(u,v),分类讨论。

设一行的点数为 d ,这样的复杂度是 O(\frac{n}{d}d^2)=O(nd) 的。

注意,对于每次转移,还需要记录最优方案。反向递归这些方案回答第二问。

我们按照转移顺序反向标记出那些点可能达到最优解,找出所有包含在最优转移中的“左上,右上,上”边,它们组成一个DAG。

接下来就是上一题了,求有源汇上下界最小流即可。

[评测记录] ()

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

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

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

评测记录

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

评测记录

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

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

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

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

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

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

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

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

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

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

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

去日本旅游的黑猫警长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/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)

对于U点,总是无要求,则连边 (U,T,[0,\inf],0),(S,U,[0,\inf],0)

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

对于原图的边 (u,v,c,f) , 考虑分段讨论可以采取怎样的变化。

对于原图中已有的流量,连边 (u,v) 并限制流量恰好为 f。

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

评测记录

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

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

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

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

评测记录

  1. 任意行或列的部件数不能超过整个芯片总部件的 A/B 这个限制。

    没有什么好的处理方法,也不存在单调性,只能考虑枚举芯片总部件数,这样能够确定行和列的限制。

    现在转化成了若干个这种问题 : 限制每行每列最多 lim 个,问最多能放置多少个。

    直接枚举需要 O(n^2) 次判定,太慢了。

    考虑我们枚举的芯片总部件给了这张图传了什么信息,不难发现就只有对于行的限制。

    而行的容量最多 n ,我们直接 O(n) 枚举这个限制,然后算出合法的总部件数就好了。

提交记录

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

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

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

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

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

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

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

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

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

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

提交记录

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

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

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

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

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

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

评测记录