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