回归梦想

网络流24

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 莫比乌斯反演(2) 队列(2) 题解(271)

/ 注册

全部文章 / 网络流24 （共11篇）

[CTSC1999]家园 / 星际转移问题

[CTSC1999]家园 / 星际转移问题题意： • 由于人类对自然资源的消耗，人们意识到大约在2300 年之后，地球就不能再居住了。于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。现有n个太空...

网络流分层图

2021-01-19

0 594

餐巾计划问题[网络流24题]

题意： • 一个餐厅在相继的N 天里，每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为p分；或者把旧餐巾送到快洗部，洗一块需m天，其费用为f 分；或者送到慢洗部，洗一块需n 天(n>m)，其费用为s<f 分。每天结束时，餐厅...

ing **** 网络流思维

2021-01-19

0 606

P4009 汽车加***驶问题

题目描述：题解：看了很多题解，无论什么解法都绕不开分层图在本题中加满油的车每次可以移动K步，那么我们就可以建立一个K+1层的分层图，表示汽车油量k的状态（油量0...k），然后根据题目要求建图首先我们规定(k从1开始)第k层第i行第j列点编号为(k-1) * n * n + (i-1) * n...

网络流分层图

2021-01-18

0 669

[ZJOI2010]网络扩容[网络流24题]

[ZJOI2010]网络扩容[网络流24题] 题意：给定一张有向图，每条边都有一个容量 c 和一个扩容费用 w。这里扩容费用是指将容量扩大 1 所需的费用。求：在不扩容的情况下，1 到 n 的最大流；将 1 到 n 的最大流增加 k 所需的最小扩容费用题解：第一问好说就是跑最大流，关键...

网络流

2021-01-18

0 640

[网络流24题]P4014 分配问题

题目描述有 nn 件工作要分配给 n 个人做。第 i 个人做第 j 件工作产生的效益为 cij。试设计一个将 n 件工作分配给 n 个人做的分配方案，使产生的总效益最大。题解：第一反应裸的二分图最优匹配最小总效益就是把边取负值求最大总效益即可网络流也可以做，先将源点S与每个人连一条容量为1，费...

最小费用最大流网络流二分图最佳完美匹配

2021-01-16

0 639

[网络流24题]P3254圆桌问题

题目：假设有来自n 个不同单位的代表参加一次国际会议。每个单位的代表数分别为ri, i=1,2,...,n。会议餐厅共有m张餐桌，每张餐桌可容纳ci (i=1,2,...,m)个代表就餐。为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。...

ing *** 网络流

2021-01-16

0 623

NC 213820 [网络流24题]最长递增子序列问题

NC 213820 [网络流24题]最长递增子序列问题题目: • 给定正整数序列x1 ,...... , xn。（1）计算其最长递增子序列的长度s。（2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为...

网络流 dp

2021-01-15

0 797

NC213818 [网络流24题]魔术球问题

例2：NC213818 [网络流24题]魔术球问题题目： • 假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，...的球。（1）每次只能在某根柱子的最上面放球。（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。试设计一个算法，计算出在n根柱子上最多能放多少个球。例如...

匈牙利算法 *** 网络流

2021-01-15

0 762

P4015 运输问题

P4015 运输问题@[toc] 题目描述：输入格式：输出格式：两行分别输出最小运输费用和最大运输费用。输入输出样例：输入 #1 2 3 220 280 170 120 210 77 39 105 150 186 122 输出 #1 48500 69140 题解：最小费用最大流(MC...

最小费用最大流费用流最大流网络流

2020-06-26

0 538

P4011 孤岛营救问题

P4011 孤岛营救问题@[toc] 输入输出样例输入 4 4 9 9 1 2 1 3 2 1 2 2 2 0 2 1 2 2 0 2 1 3 1 0 2 3 3 3 0 2 4 3 4 1 3 2 3 3 0 3 3 4 3 0 4 3 4 4 0 2 2 1 2 4 2 1 输出 14 题意...

状态压缩 bfs

2020-06-26

0 581