网络流24题

zrzring 2020-11-18 PM 15℃ 0条

本文出现的$S$均为超级源点,一般从该点流出的流量为inf,且没有前驱,$T$均为超汇,为全图的流量最终汇入点,且没有后继

搭配飞行员

题意:给你$m$对可以匹配的人,求最大匹配数

二分图匹配,没啥好说的,$S,T$就完事了

太空飞行计划

题意:给你$m$个试验,$n$个器材,每个实验需要$n$个器材中的某些器材,每个器材有一个花费,每个试验完成会获得一定报酬,求最大利润

考虑每个试验对应的多个器材,而每个试验要做,就必须全选需要的器材,我们对$S$连边到实验,流为报酬,对器材连边到$T$,流为花费,连试验需要的器材,流为inf,答案为所有实验的报酬和减最大流

为什么是这个答案,如果对于一个实验集合它报酬大于它的器材集合的花费,那么最大流就是器材的花费,反之,最大流就是要舍弃的实验集合(因为做这个实验集合亏钱),前者表示你要做这些实验,因为它能赚钱,于是这代表了利润等于报酬减成本,后者表示你不做这些实验,直接舍弃全部这些实验的报酬

LibreOJ的SPJ非常奇怪,我的AC代码是在luogu提交的,LibreOJ根本通过不了(即使后来把行末空格去掉)

最小路径覆盖

题意:求一个DAG的最小路径覆盖

经典题目,拆点,将一个点拆成一个入点和一个出点,分别放到两个集合中,将题目给的边对应地连起来,就是二分图匹配了

原因很简单,匹配一对就是连了两条边,将两条路径合并成一条路径,那么我们连最多的边,最后的路径数量就最少

魔术球

题意:从$1$开始往$n$个柱子上依次填数,每次填数保证和当前柱子顶部的数加起来是一个完全平方数

啊我只写了个贪心,好像网络流和他思路差不多,这个贪心非常好想,你每次就看着有数的位置能放就放,不能放就开新柱子

网络流写法待填坑qwq

圆桌会议

题意:$m$个国家每个国家$r_i$个代表在$n$个桌子上吃饭,给定一种方案使得每个桌子做的人都来自不同国家

还是考虑利用流满表示可行状态,于是我们从$S$连向每个国家,流为$r_i$,从每张桌子连向$T$,流为桌子能坐的人数,从每个国家连向每张桌子,流为$1$,这样我们可以用流量是否等于所有国家的人数来判断有没有合法方案,最后输出方案去看残量网络那些单位到哪些桌子剩余流量为0即可

最长不降子序列

题意:给定一个长度为$n$的正整数序列,求

  1. 计算其最长不降子序列的长度
  2. 计算从给定的序列中最多可取出多少个长度为$s$的不降子序列
  3. 如果允许在取出的序列中多次使用$x_1$和$x_n$ ,则从给定序列中最多可取出多少个长度为$s$的不降子序列

第一问dp随便搞,第二问为了保证每个数选一次于是拆点并设置自己连自己的流量为1,然后把能接过去的关系连上,这个能否接上的关系已经在$dp$中求出来了,最后$S$连每个长度为$s$的不降子序列的头,尾去连$T$即可

第三问把$1$和$n$的自连边,$S$到$1$和$n$到$T$的流量设置为inf即可

试题库

题意:n个题抽m个题组成试卷,每个题都有一个类型集合,加入卷子以后可以变成该集合任意类型,组成的试卷对每种类型都有一个数量需求

裸题,源点到每个题连流量为1的边,每个题往自己的类型集合连流量为1的边,每个类型集合往汇点连流量为数量需求的边,跑最大流即可

方格取数

题意:n*m的方格矩阵,每个方格中有一个正整数,现要从方格中取数,使选取的任意两个数所在方格没有公共边,且取出的数的总和最大

题意很清楚,因为是选取,考虑转换成最小割,那我们就全选以后去掉一些数来满足条件就好了,去掉的数就是最小割

怎么建图,对棋盘黑白染色,使得任意两个相邻的格子颜色不同,源点向黑点连流量为黑点的数字的边,白点向汇点连流量为白点数字的边,相邻的格子连inf边,跑最大流求出最小割,然后用全局数字的sum减去即可

正确性考虑最小割的性质,割完以后S,T不联通,但是我们对于题目要求的联系都没有被割,在这个情况下留下的数就和题目要求的一致了

餐巾计划

题意:餐厅在第$i$天需要使用$r_i$张餐巾,使用过的餐巾会脏,脏餐巾不可使用,但可以送去快洗店或慢洗店清洗,商店里餐巾的售价为$p$,求$n$天内的最少花费

考虑最大流必须等于每天使用的餐巾数目才可以跑费用流,那我们设$S$为商店流向每一天,可以买无限多的纸巾于是流为inf

对于餐巾,我们有用餐巾盒脏餐巾两个状态,用餐巾这个过程要流入$T$,但$T$出不来,无法让用过的餐巾洗过再用,故我们把一天拆成两个点$p1,p2$,其中$p1$接受没用过的餐巾,$p2$接受用过的餐巾

把$p1$连向$T$,流为$r_i$,$S$连向$p2$,流为$r_i$,相当于为当天流入用过的餐巾,再把$p2$连向直接去洗洗完回来的那一天的$p1$,表示洗完接着用,由于我们干净的纸巾可以无限保留,每一天的$p1$要流向后一天的$p1$,我们就表示出了所有的状态了

评论


您还没有登录呦


登录 注册
Title - Artist
0:00