网络流24题

第一题

P2756 飞行员配对方案问题

求二分图匹配,输出谁和谁匹配

使用反向边是否存在流量来输出路径。

第二题

P2762 太空飞行计划问题

求有向图的最大权闭合子图

将正权点连接s,容量为点权,负权点连接t容量为点权绝对值,所求得的一个割将图分为两部分,我们发现所有正点权的和减去该简单割,便是与s相连的闭合图的权,因为最小割所以最大权闭合图(即给定常数c,求c-a的最大值,等价于求c减去a的最小值)。注意跑完最大流以后,与s相连的点构成的点集就是最大权闭合图。学会了使用bfs之后 的lv数组来输出路径

第三题

P2764 最小路径覆盖问题

求DAG的最小路径覆盖

用原图建立一个两层的新图,如果原图中存在边i->j我 们建立的新图就有第一层的点i流到第二层的点j,最后建立超级源点流向 所有的第一层图的点,建立超级汇点,由所有第二层的图流入,用DAG的总点数减去去所求的最大流就是最小路径。

在构造的二分图中的最大流映射回原图,发现每个点最多有一个入度,一个出度,显然整个图形成了一些不相交的链,于是点数减去边数就是联通块的个数。即总点数减去匹配数就是最小路径数。

第四题

P2765 魔术球问题

依旧是是一个最小路径覆盖的问题,我们考虑把球当作点,把盒子当成路径,那么很明显,连边方式就是i->j当且仅当i<=n且j<=n且i+j=k^2.
但是这样子做我们只能解决这样一个问题: 给你从1到n的n个球我们可以找到最少的盒子来装球。

仔细分析发现题目给的问题可以二分处理,我们二分来判断n个盒子能不能装到k个球就可以了。

第五题

P3254 圆桌问题

给m组人,每个人要分到不同的桌子上,每个桌子可以一定量的人,组内的人不能坐在一个桌子上, 网络流问题,s连到组,流量组内人数,桌子连到t,流量为可以坐下的人数,组与桌子自由组合, 流量为1。

第六题

P2766 最长不下降子序列问题

让你求一个数列的最长不下降子序列的长度k

然后求这个序列最多可以分出多少个长度为k的子序列,

再求如果可以多次使用第一个元素和最后一个元素,可以分出多少个长度为k的子序列

我们考虑到每个元素dp的值(dp[i]表示以i结尾的最长不下降子序列的长度),并以dp值为标准,给所有点分层,并给所有第一层的点连s,所有最后一层的点连t, 如果i<j且a[i]<=a[j]我们就连一条边i->j,如此如果每当从s流到t,就是一个子串,考虑到一个点只能用一次,拆点限流就可以了。

第七题

P2763 试题库问题

给你一个试题库,告诉你每个题目的类型(一个题目可能属于多种类型),让你 用这些题为每个类型组一套题(告诉了你每套题包含的题数),每道题只能用一次,
类型在左,题目在右,s连类型,流量为该套题的题数,类型连题目流量1,题目连 t流量1,如果最大流不够要求的题目数量,说明无法组成套题。

第八题

P2775 机器人路径规划问题

什么怪东西,明明是深搜题

第九题

P2774 方格取数

有一个 m 行 n 列的方格图,每个方格中都有一个正整数。现要从方格中取数,使任意两个数所在方格没有公共边,且取出的数的总和最大,请求出最大的和。

对于格子我们令k=行数加列数,

对于所有的k&1==1内部,无边,

对于所有的k&1==0内部,无边。

于是取走元素就成了:

拿走点,使得这些点覆盖所有边,于是剩下的点就是独立的了, 没有边互相连。就是我们要的答案,所以就成了 最小点覆盖二分图

第十题

P1251 餐巾纸计划

此处不方便证明,详情见: 建图与证明

第十一题

P2770 航空路线问题

给你一个城市数组,这些城市从左往右分别对应从东到西, 要求你从最西边的城市出发,到达最东边的城市,在从最东边的城市出发,到达最西边的城市 除了最西边和最东边的城市以外,其他城市只能经过一次 让你求最多经过多少城市,

考虑最大流,s连最西边的城市,最东边的的城市连t,容量2,对于他给的边只连从东到西的边, 对于一个城市只经过一次考虑拆点限流即可。