标签:网络流

7 篇文章

P2774 方格取数问题
题面 洛谷 P2774 题目描述 在一个有 $m*n$ 个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 $2$ 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。 输入格式 第 1 行有 2 个正整数 $m$ 和 $n$,分别表示棋盘的行数和列数。接下…
[ZJOI2009]狼和羊的故事
题面 描述 洛谷 P2598 狼爱上羊啊爱的疯狂,谁让他们真爱了一场; 狼爱上羊啊并不荒唐,他们说有爱就有方向…… Orez 听到这首歌,心想:狼和羊如此和谐,为什么不尝试羊狼合养呢?说干就干! Orez 的羊狼圈可以看作一个 n*m 个矩阵格子,这个矩阵的边缘已经装上了篱笆。可是 Drake 很快发现狼再怎么也是狼,它们总是对羊垂涎三尺,那首歌只…
网络流 24 题 – 试题库问题
题面 洛谷 P2763 & LOJ #6006 题目描述 假设一个试题库中有 $ n $ 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 $ m $ 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。 输入格式 第 $ 1 $ 行有 $ 2 $ 个正整数 $ k $ 和 $ n $。$…
[SCOI2007] 蜥蜴
题面 在一个 r 行 c 列的网格地图中有一些高度不同的石柱,一些石柱上站着一些蜥蜴,你的任务是让尽量多的蜥蜴逃到边界外。 每行每列中相邻石柱的距离为 1,蜥蜴的跳跃距离是 d,即蜥蜴可以跳到平面距离不超过 d 的任何一个石柱上。石柱都不稳定,每次当蜥蜴跳跃时,所离开的石柱高度减 1(如果仍然落在地图内部,则到达的石柱高度不变),如果该石柱原来高度…
洛谷 P2764 最小路径覆盖问题
题面 题目传送 给定有向图 $G=(V,E)$ 。设 $P$ 是 $G$ 的一个简单路(顶点不相交)的集合。如果 $V$ 中每个定点恰好在$P$的一条路上,则称 $P$ 是 $G$ 的一个路径覆盖。$P$中路径可以从 $V$ 的任何一个定点开始,长度也是任意的,特别地,可以为 $0$ 。$G$ 的最小路径覆盖是 $G$ 所含路径条数最少的路径覆盖。…
洛谷 P2756 飞行员配对方案问题 & LOJ #6000「网络流 24 题」搭配飞行员
题面 洛谷 P2756 飞行员配对方案问题 LOJ #6000.「网络流 24 题」搭配飞行员 因为 LOJ 上的版本比较简洁,所以就放这个版本的题面了。 飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机,这种飞机每架有两个驾驶员,需一个正驾驶员(英国)和一个副驾驶员(外籍)。由于种种原因,例如相互配合的问题,有些驾驶员不能在同一架飞机上飞…
网络流 EK (Edmond-Karp) 算法详解 求解最大流和费用流问题
前言 问题 有 $n$ 个城市,$m$ 条单向铁路连接了这些城市。每条铁路可以售 $s_i$ 张票。现在人们要从 $S$ 城去 $T$ 城,假设他们都有足够的钱去购买车票,那么最多有多少人能到达 $T$ 城? 思路 要使 $S$ 的人到达 $T$ ,首先要找到一条从 $S$ 到 $T$ 的通路(否则就到不了 $T$ 了)。显然,这条路最多只能通过其…