网络流题目记录

wamaker posted @ 2010年9月21日 02:03 in 图论 with tags 网络流 , 1895 阅读

同之前的线段树题目记录一样,持续更新中,在此膜拜一下小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~膜拜!

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

Adobe Photoshop hat kürzlich ein neues Tool namens Generative Fill veröffentlicht, das die KI-Technologie Firefly nutzt, um Benutzern dabei zu helfen, ihre Fotos auf aufregende Weise zu verbessern. photoshop generative fill aktivieren Dieses Tool ermöglicht Benutzern das einfache Erweitern von Fotos, das Hinzufügen oder Entfernen von Objekten mithilfe einfacher Textaufforderungen und bietet im Vergleich zu anderen Tools wie Content-Aware Fill mehr Kontrolle.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter