【泛做】网络流乱搞记录

做了点网络流题目,算是对网络流的一个复习吧。

感觉现在建起图来已经可以算是得心应手了.jpg

打星的题目都比较有趣。大部分题目可能没有数据范围,当作 O(网络流能过) 就好了。

虽然现在都考模拟费用流,建图费用流已经是历史的眼泪了。

最大流

*[UVA11167] Monkeys in the Emei Moutain

大概说有 $n$ 只猴子,猴子们在某个时间段需要喝 $v_i$ 时间的水,各个单位时间段最多允许 $m$ 只猴子同时喝水,问猴子们能否成功喝水并输出一个可行的方案,输出方案的时间段区间要从小到大排序并且合并连续的区间。

$1\leq l_i,r_i\leq 50000,n\leq 100$ 。

考虑暴力建图,我一开始的思路是对于每个时间点拆成两个点 $t’,t$ 之间连 $f=m$ 的边,然后猴子 $i$ 向一个区间的点连 $f=+\infty$ 的边,源点向猴子连 $f=v_i$ 的边。这样边数可以通过线段树来搞成 $T\log T$ 的。

然而上面这个建图肉眼可见的不是正解。考虑向区间模型上靠,因为猴子数很少,最多有 $O(n)$ 个本质不同的区间端点。于是可以考虑把上面那种做法中没有用到的多个时间点合并成一个,并且把 $f=m$ 改成 $f=k\times m$ 。依旧做就好了。

[UVA11082] Matrix Decompressing

给出一个 R 行C 列的正整数矩阵,设前 $A_i$ 项为其前 $i$ 行所有元素之和,$B_i$ 项为其前 i 列所有元素之和,已知 R,C,A,B,找出一个满足条件的矩阵。其中每个元素都是1~20 的正整数。

sb 题。考虑源向每一行连 $f=r_i$ 的边,每一列向汇连 $f=c_i$ 的边,行列再向每个点连 $f=\infty$ 的边。同时给中间的每条边设置一个上下界 $1$ ,流就完了。

然后发现并不用建出中间的那一排点来。并且下界如果为 $1$ …就可以直接上下界各减 $1$ 然后跑普通的流即可。

**[ACM/ICPC NEERC2009] Inspection

求解无权 DAG 的最小路径覆盖。特别的,路径可以重复走。

很神奇一道题。神奇在我在 check 自己的 Sol 的时候发现了这么一回事:

对于图中的每个点 $i$,设 $d_i$ 为( $i$ 的入度 - $i$ 的出度)的值,按照 $d_i$将图中的点分类:

$d_i\lt 0$ 的称为“入少出多”的点,$d_i\gt 0$ 的称为“出少入多”的点,$d_i=0$ 的称为“入出相等”的点。则有:

定理:有向无环图中最小边路径覆盖的值等于图中所有“入少出多”的点的 $d_i$ 绝对值之和。

这还是比较显然的,注意到这个定理是在陈述「边覆盖」就不难理解了。 然后借此先说 Sol 1:

Sol 1

考虑本题和不能重复走的最小路径覆盖有什么区别,那必然是存在一些路径可以重复经过。我断言,这样的路径必然满足起点 $d_i>0$,终点的 $d_i\lt0$ ,否则没有必要重复经过。考虑某条这样的路径 $(s:t)$ 每被重复经过一次,就必然是为了将 $t$ 之后的某条路经和 $s$ 之前的某条路径拼插起来,这样原来需要 $2$ 次现在就只需要 $1$ 次。

于是考虑直接对着这个跑一次最大流即可,各个地方的流量都是 $1$ ,拿定理中的答案减去这个最大流就好了。

Sol 2

…发现这题就是一个带下界的最小流。于是就跑一个带下界的最小流即可。

[ACM/ICPC NWERC 2007] March of the Penguins

有一群企鹅,一些冰。企鹅们在快乐地玩耍。

给出每个企鹅的最大跳跃距离(大家都一样),再给出冰的坐标和上面存在的企鹅个数和允许跳跃的次数,问有哪些冰是可以将所有的企鹅汇聚起来的。

比较简单一题。之前的想法是这么建图(事实上就是这么建图):源点向每块冰连 $n_i$ 的边代表原有企鹅,每块冰拆成俩点限制跳跃次数。然后冰之间根据跳跃距离连边就好了。

但是自己的处理方式不是很到位。我的想法是枚举每个点作为汇点跑一遍最大流再去 check 是否满流,后来发现其实并不需要,只需要一个跑一遍最大流就好了。因为如果对于某个 $i$ 满流,他要么可以将这一份满流输送给其他点,要么就是被其他点数输送过来的。

*[ACM/ICPC Hangzhou 2005] Duopoly

C公司有一些资源,每种只有1个,有A、B两个公司分别对其中一些资源进行分组竞标,每组竞标对一些资源出一个总价。问C公司的最大收益。

谔谔,感觉有被降智到。

一开始想了很多奇奇怪怪的建图方式,都是错的。后来看了题解发现…其实本质上根本不关心每种资源到底是怎么分配的,只关心某些资源的组合能够带来多少收益。于是建图就不需要考虑每种资源了,直接对 A 和 B 的所有竞标分立两侧,有冲突的就连边,跑一个最小割就好了。

[经典题] 二分图带权最大独立集

给定一张二分图,图里面每个点会带一个权。求权最大独立集。

将权调整到 $\rm S\to …$ 和 $\rm …\to T$ 上 。就变成睿智最小割了。我为什么要整这个题!?

[经典题]最优调度(公平分配) /LA3231 Fair Share

m个任务n个处理器,一个任务只能在可供运行的两个机器中的其中一个上运行,问怎样分配使得任务最多的机器尽量少。

那必然是要二分答案。之后流一下看看与源点相连的每个任务那条边是否满流就好了。

*[UVA11248] Frequency Hopping

给定一个有向网络,每条边均有一个容量。问是否存在一个从点1到点N,流量为C的流,如果不存在,是否可以恰好修改一条弧的容量,使得存在这样的流。

比较有意思的题,考虑如果要修改,那必然是要修改最小割上的边。然后就把最小割求出来,再枚举每一条边。但是注意到不需要每次重新求一遍最大流,可以直接在原图上增广。这个技巧需要心领神会。

*[ACM/ICPC Taejon 2002] The K-league

Taejon:大田,似乎是韩国的某城市,长见识了。

有n个队伍进行比赛,每场比赛,恰好有一支队伍取胜、一支队伍败。每个队伍需要打的比赛场数相同。

给你每个队伍目前已经赢得的场数 $done_i$,再给你一个矩阵,表示队伍 i 和队伍 j 还需要打的比赛数,问你哪些队伍有可能获得冠军(胜场最多的即为冠军,可以并列)。

这题比较神。首先一个观察就是可以独立求出每个队伍是否可以夺冠。考虑首先要钦定当前队伍赢得所有未竟比赛,设这个数量为 $s$。之后考虑就是能否有一种安排策略使得其它的队伍获胜场数均 $\leq s$。

发现这就是一个上面提到过的公平分配模型。考虑将每一场比赛分配给每支队伍。把一支队伍的最多获胜场次设为 $s-done_u$ ,然后检查一下每个比赛的那条边是否满流就好了。

**[UVA10779] Collector’s Problem

现在有包括了Bob在内的 n 个小朋友,m 种游戏卡片,Bob可以和其他人交换卡片,除了Bob,每个人的交换原则都是只给出自己的拥有多张卡片,接受自己没有的卡片。的问他最后有多少不同的卡片。

$n\leq 10, m\leq 25$ 。

考虑如果 $m$ 稍微小一点,比如 $10$ 之类的就可以直接状压了。$f_{s_1,s_2}$ 表示现在考虑了 Bob 的朋友集合为 $s_1$ ,拥有的卡牌集合为 $s_2$ 是否可行。这样每次转移就可以刷个表。复杂度 $O(2^n\cdot n\cdot m\cdot 2^m)$ 。

m=10好像也不是很能过

于是考虑正经建图,还是比较仙的。考虑怎么正确对待「只给出自己的拥有多张卡片,接受自己没有的卡片」这个限制,发现这个限制十分的强,限制了每个小朋友已经有的卡片数目在过程中也不能 $\lt1$ 。于是对于每个小朋友关心的就只在于其 $>2$ 的数量的卡牌。

考虑怎么建图(好神啊)。 大概就是说小伙伴只是用来换的工具人,并不关心他们怎么分配,只关心最后每张牌是否可以拿到。于是就可以考虑从源点向每一张牌连一张 $f=a_i$ ,其中 $a_i$ 是 Bob 原有的卡的弧,每张牌向 $T$ 连 $f=1$ 的弧。考虑怎么于小伙伴们交互,如果小伙伴 $j$ 没有某张牌 $i$ ,就连 $i\to j$ 流量为 $1$ ;如果如果小伙伴 $j$ 的某张牌数量 $b_{j,i}>1$ ,就向 $i$ 连 $f=b_{j,i}-1$ 的边。流一下就好了。

费用流

*[ACM/ICPC Taiwan 2005] Optimal Bus Route Design

给出一个有向图,你需要让每一个点都恰好在一个环中,并且边权和最小。

…喜闻乐见的找性质题。

首先转化一下,「每个点恰好在一个环中」=「每个点后继的唯一」。因为每个点都显然会有一条出边一条入边,所以直接拆点跑一个 KM 或者费用流就一定是合法解。

……一开始的时候感觉是个裸匹配,然后回忆起曾经做过的无向图找非简单环的计数题似乎答案是个贼大的数,就十分懵逼。

**[LA4043] Ants

给定一些黑点白点,要求一个黑点连接一个白点,并且所有线段都不相交。

$n\leq 500$ 。

感觉这题的俩做法都很经典有趣啊。

Sol 1

大概是需要深刻地发现一些性质。考虑如果四个点连两条线段想要不交的话,那么感性理解一下要么并排着竖着连,要么并排着横着连,随便旋转一下坐标系可以知道两者是等价的。那么考虑如何横着选,发现如果对于第一列的点如果各自找与自己距离最小的点,就一定不会相交。进一步考虑全局,如果最后点对之间的总距离之和最小那么同样不会交。所以做一遍 KM 就好了。

Sol 2

考虑暴力分治。感觉这个做法没点经验是想不出来的。考虑上面 KM 算法所找的最近点对完全可以分治做。具体的,先随机选一个点,然后让其他的点按照以当前点为坐标原点的极角排序,观察最小的那个:

1、如果颜色不同,那么就直接匹配。

2、如果颜色相同,就继续找更大的,直到找过的所有点中两种颜色数量相等且当前点与源点颜色不同。此时头尾匹配一下,就可以分治成两部分继续做了。

[ACM/ICPC Harbin 2010] 货物运输

费用为 $af^2$ 的费用流。

主要就是用了这个技巧。考虑常见的拆平方技巧

然后就可以根据值域拆成多个弧来做了。

[ACM/ICPC Dhaka 2006] Paint the Roads

一个 $n$ 个点 $m$ 条带权有向边的图,要给边染色,染色的边形成若干个回路且每个点都恰好属于其中 $k$ 个回路。问最少要染多少边权和的路。

考虑有了前面的铺垫,属于 $k$ 个回路可以直接拆成 $k$ 组匹配。做就好了。

*[ACM/ICPC World Final 2011] Chips Challenge

有一个芯片,芯片上有 $N*N(1≤N≤40)$ 个插槽,可以在里面装零件。
有些插槽不能装零件,有些插槽必须装零件,剩下的插槽随意。
要求装好之后满足如下两条要求:

1、第 i 行和第 i 列的零件数目必须一样多($1≤i≤N$)。

2、第 i 行的零件数目不能超过总的零件数目的 $A/B$($1≤i≤N$,$0≤A≤B≤1000$,$B≠0$)。

求最多可以另外放多少个零件(就是除掉必须放的)。如果无解输出impossible。

学到了,大概是发现有些约束互相影响,或者是个变量不好处理的时候,可以考虑枚举这个约束。

大概就是考虑枚举零件总数 $s$ ,然后去check这个结果是否合理。考虑怎么 check,不难知道要行列二分图那种感觉,中间钦定为 $1$ 的就连上下界均为 $1$ 的边,钦定为 $0$ 的就不连边,没钦定的就连上界为 $1$ 的边。然后求出此时可以放的部件数。如果大于枚举的 $ans$ 就说明合法。

于是最后大概要跑一个有源汇上下界最大费用最大流?