网络流 - Page 9

「网络流24题」餐巾计划问题
题目描述 Description一个餐厅在相继的N天里，每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为p分；或者把旧餐巾送到快洗部，洗一块需m天，其费用为f分；或者送到慢洗部，洗一块需n天(n>m)，其费用为s<f分。每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，...
02014年3月8日7,290费用流

「网络流24题」圆桌聚餐
«问题描述：假设有来自m个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri(i=1,2,3...m),。会议餐厅共有n张餐桌，每张餐桌可容纳ci(i=1,2...n)个代表就餐。为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。 «编程任务：对于给定的代表数和餐桌数以及餐桌容量，编程计算满足要求的代表就餐方案。 «数据输入...
32014年3月8日5,308最大流
「网络流24题」魔术球问题
Description假设有n根柱子，现要按下述规则在这n根柱子中依次放入编号为1，2，3，4的球。（1）每次只能在某根柱子的最上面放球。（2）在同一根柱子中，任何2个相邻球的编号之和为完全平方数。试设计一个算法，计算出在n根柱子上最多能放多少个球。例如，在4根柱子上最多可放11个球。编程任务：对于给定的n，计算在n根柱子上最多能放多少个球。InputFormat文件第1行有1个正整数n，表示柱子数。OutputFormat程序运行结束时，将n...
42014年3月7日8,782最大流
「网络流24题」运输问题
题目描述 DescriptionW公司有m个仓库和n个零售商店。第i个仓库有ai个单位的货物；第j个零售商店需要bj个单位的货物。货物供需平衡，即 sum(si）=sum(bj)。从第i个仓库运送每单位货物到第j个零售商店的费用为cij。试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。编程任务：对于给定的m个仓库和n个零售商店间运送货物的费用，计算最优运输方案和最差运输方案。输入描述 InputDescription的第1行有2个...
02014年3月7日4,162费用流
「BZOJ1189」[HNOI2007] 紧急疏散evacuate
Description发生了火警，所有人员需要紧急疏散！假设每个房间是一个NM的矩形区域。每个格子如果是'.'，那么表示这是一块空地；如果是'X'，那么表示这是一面墙，如果是'D'，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没...
62014年3月7日7,359最大流,二分法,广度搜索
「CODEVS1034」家园
题目描述 Description由于人类对自然的疯狂破坏，人们意识到在大约2300年之后，地球不能再居住了，于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。现有n个太空站处于地球与月球之间（编号1..n），m艘公共交通太空船在其中来回穿梭，每个太空站Si可容纳无限的人，每艘太空船pi只可容纳Hpi人。对于每一艘太空船pi，将周期性...
02014年2月28日3,386最大流
「网络流24题」最小路径覆盖问题
Description问题描述：给定有向图G=(V,E)。设P是G的一个简单路（顶点不相交）的集合。如果V中每个顶点恰好在P的一条路上，则称P是G的一个路径覆盖。P中路径可以从V的任何一个顶点开始，长度也是任意的，特别地，可以为0。G的最小路径覆盖是G的所含路径条数最少的路径覆盖。设计一个有效算法求一个有向无环图G的最小路径覆盖。编程任务：对于给定的给定有向无环图G，编程找出G的一个最小路径覆盖。InputFormat文...
02014年2月28日9,415最小割
「JoyOI1982」武器分配
描述Description后勤部队运来一批武器（机枪和盔甲）。你要把这些武器分配给手下的marine们（每人一部机枪，一套盔甲）。可是问题来了。。。这些武器的型号不相同（武器是由出价最低的承包商制造的），把一部m型的机枪和一套n型的盔甲分配给一个marine得到的不满意值为(m-n)^2（每个marine当然希望自己得到的武器是同一型号的）。你的任务就是把a部机枪和b套盔甲分配给手下n个marine。使他们的不满意值之和最小。输入格式InputF...
02014年2月25日3,048费用流
「BZOJ1877」[SDOI2009] 晨跑
DescriptionElaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天从寝室出发跑到学校，保证寝室编号为1，学校编号为N。Elaxia的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的...
22014年2月23日5,357费用流
「BZOJ1066」[SCOI2007] 蜥蜴
Description在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能落脚。任何时刻不能有两只蜥蜴在同...
02014年2月22日7,100最大流
「CODEVS1913」数字梯形问题
题目描述 Description给定一个由n行数字组成的数字梯形如下图所示。梯形的第一行有m个数字。从梯形的顶部的m个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。规则1：从梯形的顶至底的m条路径互不相交。规则2：从梯形的顶至底的m条路径仅在数字结点处相交。规则3：从梯形的顶至底的m条路径允许在数字结点相交或边相交。对于给定的数字梯形，分别按照规则1，规则2，和规则3计算出从梯形的顶至底...
02014年2月21日3,979费用流
「BZOJ1834」[ZJOI2010] network 网络扩容
Description给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求：1、在不扩容的情况下，1到N的最大流；2、将1到N的最大流增加K所需的最小扩容费用。Input输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。Output输出文件一行包含两个整数，分别表示...
02014年2月21日7,852费用流,最大流