网络流题目记录

同之前的线段树题目记录一样,持续更新中,在此膜拜一下小HH

hdu 3081 Marriage Match II

n男n女过家家,女生可以挑没有跟她吵过架的男生匹配,也可与没有跟她朋友吵过架的男生匹配(可以认为是她喜欢的男生)。每轮游戏,每个女生选个她没选过的男生,问游戏最多能进行几轮?

构图:先用并查集处理女生友情的传递。每个女向她喜欢的所有男生以及她朋友喜欢的男生连一条容量为1的边。二分最大能进行的轮数ans,源点向每个女生连一条容量为ans的边,每个男生向汇点连一条容量为ans的边。判断最大流是否等于ans*N;

 

hdu 3277 Marriage Match III

同上,每个女生可以跟最多K个她不喜欢的男生匹配。

构图:每个女生拆为两个点Gi1,Gi2。Gi1连一条容量为K的边到Gi2。每个Gi2连一条容量为1的边到女生i不喜欢的男生,源点连容量为ans的边到每个Gi1。其余同上

一开始用Dinic,无限TLE~~~ T_T 。万般无奈下,只好上Qinz大牛的博客膜拜了ISAP的模板,再结合网上各路神牛的论文,终于得出了一份自己的ISAP模板~,提交果断AC~

 

hdu 3416 Marriage Match IV

有向图,求起点到终点的最短路的条数。

构图:求最短路,起点到所有点的最短路,所有边反向,求终点到所有点的最短路,对于边如果起点到u的距离加终点到v的距离加这条边的权值等于最短路长,那么在网络流的图中加一条u指向v,权值为1的边。求起点到终点的最大流。

poj 3281 Dining 

N头牛,D种饮料,F种食物,每天牛吃一种食物一种饮料,食物和饮料都只有一份。问最大满足多少头牛。

构图:由于每头牛只需一份饮料和食物,所以每头牛要拆为两点,连容量为1的边。起点到所有食物连容量为1的边,饮料到汇点连容量为1的边。牛再和食物,饮料连。Dinic 0MS毫无压力。

poj 2135 Farm Tour 

求起点到终点再回起点的最短路径。不能走重复的路。

构图:第一次写费用流。用的是朴素的spfa。费用是距离。源点到1连一条容量为2的边。终点到汇点连容量为2的边。每条路径的容量都为1.直接水过。

poj 2711 Leapin' Lizards 

图上有些柱子,开始时,一些蜥蜴在柱子上,当蜥蜴跳离柱子时,柱子高度降1,蜥蜴不能跳到高度为0的柱子上,蜥蜴跳跃的距离为D,求有多少蜥蜴能够跳出来。

构图:把每个有高度柱子拆为两点,ai,bi,ai->bi容量为柱子高度。源点接到有蜥蜴的柱子ai上,能一步跳出去的柱子的bi接到汇点,容量INF,距离为D的任意两格子都连容量INF的边。求解最大流。求曼哈顿距离的时候出了点小问题,无限WA。注意输出,单复数是不同的。

poj 2516 Minimum Cost

有N个客户订单,M座仓库。给出订单内容和仓库库存,以及仓库到客户的费用。求满足所有客户需求的最小费用。

构图:原生态最小费用流。每种商品都是独立的,那么我们可以针对每种商品计算最小费用。从源点连容量为仓库i中k种商品库存费用为0的边到仓库i,仓库i接容量为无限,费用为到客户j的费用。如果最大流等于k的需求总量那么k就满足了。可以记录每种商品需求总量和库存总量。供不应求则输出-1 。

poj 3680 Intervals

已知N条线段的端点和线段的权值,选一些线段使权值最大,坐标轴上一点最多被覆盖K次。

构图:费用流。原打算拆点连边。感觉复杂度过不了,膜拜了传说中神一般的构图:先把点离散化,起点到第一点连权值为0,容量为K,i到i+1连权值为0容量为K的边,直到汇点。一条线段的起始点连一条容量为1权值为-w的边到结束点。

 

poj 3498 March of the Penguins

有点类似2711,把柱子改成了冰块。而冰块上有一些企鹅,企鹅们要选一块冰块聚会,聚会点要求所有企鹅都能到达。给出企鹅的跳跃距离。找出所有的聚会点。

构图:基本同2711,这回要枚举点作为汇点。只要最大流等于除这冰块上的所有企鹅个数即可作为集结点,注意冰块是0起始的(调试到半夜一直出不了样例,原来。。。。)。

 

poj 3469 Dual Core CPU

网络流经典题目。最小割。一块CPU使用A模式要耗费Ai使用B模式耗费Bi,不同CPU交换数据耗费Wij,求a到b模式工作的最小耗费。

构图:题意比较囧,总之,源点连到所有CPU权值为使用Ai,CPU到汇点的权值为Bi。不同的CPU连Wij的边。求最大流,根据最大流最小割得解。

 

poj 1149 PIGS

农夫有M猪圈,有一天他要卖猪,但他没有猪圈钥匙而顾客有(好囧)。顾客来了以后打开他能打开的所有猪圈。买走一定数量的猪,然后关门。农夫可以在关门前把剩余的猪转移到别的猪圈。问农夫最多能卖多少猪。

构图:直接以猪圈和顾客为点,数量为边,TLE了。这题构图好难,这篇文章解释得很Nice~膜拜!

 
poj 2391 Ombrophobic Bovines
F块田上有些牛,以及牛棚,要下雨了,牛要返回牛棚。牛棚的容量有限,有些无向路连接这些牛棚。给出牛棚容量,牛数,每条路径时间。求最晚什么时候牛必须全回牛棚。
构图:先拿FLOYD计算一下各个牛棚间的距离,为了避免网络流过程中出现传递,每个牛棚拆为两点,入点和出点。源点到牛棚入点连容量为牛数量的边,牛棚出点连牛棚容量的边到汇点。二分答案,如果A到B的距离小于等于mid,那么AB之间可以连边。判断最大流是否等于牛总数。
poj 3422 Kaka's Matrix Travels
有一个N*N的矩阵,每次从矩阵左上角出发,到达右下角,且只能往下或往右走。每走过一个格子,sum加上该元素(只加一次),求走了K次以后所能得到的和最大是多少。
构图:一开始以为是动态规划,但动态规划在K=1的时候有用,K>1我就不会了,好在N不大,可以用费用流来解,每个元素拆为两点,AB,Ai向Bi连容量为1,费用为该元素值的边,再连一条容量为INF,费用为0的边(保证这个格子走了一次以后还可以走第二次,且费用不算)。每个格子的B再向下边和右边的格子的A连一条容量INF,费用0 的边。最后求最大费用流。