费用流 - Page 3

「网络流24题」航空计划
«问题描述：给定一张航空图，图中顶点代表城市，边代表2城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。(1)从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点(可途经若干城市)。(2)除起点城市外，任何城市只能访问1次。«编程任务：对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。«数据输入：由文件airl.in提供输入数据。文件第1行...
12014年4月3日3,459费用流

「BZOJ3171」[TJOI2013] 循环格
DescriptionInput第一行两个整数R，C。表示行和列，接下来R行，每行C个字符LRUD，表示左右上下。Output一个整数，表示最少需要修改多少个元素使得给定的循环格完美SampleInput34RRRDURLLLRRRSampleOutput2HINT1<=R,L<=15题解可知每个点的出度=入度=1二分图+费用流S向每个点连容量1费用0的边每个点拆出的点向T连容量1，费用0的边每个格子向四周连费用0或1的边[crayon-67400e3817eb0631504...
02014年3月18日4,642费用流
「BZOJ2424」[HAOI2010] 订货
Description某公司估计市场在第i个月对某产品的需求量为Ui，已知在第i月该产品的订货单价为di，上个月月底未销完的单位产品要付存贮费用m，假定第一月月初的库存量为零，第n月月底的库存量也为零，问如何安排这n个月订购计划，才能使成本最低？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为S。 Input第1行：n,m,S(0<=n<=50,0<=m<=10,0<=S<=100...
02014年3月17日4,237费用流
「BZOJ1221」[HNOI2001] 软件开发
Description某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA,B种消毒方式的费用为每块毛巾fB，而买...
02014年3月16日4,015费用流
「网络流24题」分配问题
题目描述 Description有n件工作要分配给n个人做。第i个人做第j件工作产生的效益为ijc。试设计一个将n件工作分配给n个人做的分配方案，使产生的总效益最大。«编程任务：对于给定的n件工作和n个人，计算最优分配方案和最差分配方案。输入描述 InputDescription第1行有1个正整数n，表示有n件工作要分配给n个人做。接下来的n行中，每行有n个整数cij，1≤i≤n，1≤j≤n，表示第i个人做第j件工作产生的效益为cij输出描述 OutputD...
02014年3月11日5,115费用流
「网络流24题」负载平衡问题
题目描述 DescriptionG公司有n个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使n个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。«编程任务：对于给定的n个环形排列的仓库的库存量，编程计算使n个仓库的库存数量相同的最少搬运量。输入描述 InputDescription第1行中有1个正整数n（n<=100），表示有n个仓库。第2行中有n个正整数，表示n个仓库的库存量。输出描述 Outpu...
12014年3月11日6,104费用流
「网络流24题」餐巾计划问题
题目描述 Description一个餐厅在相继的N天里，每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为p分；或者把旧餐巾送到快洗部，洗一块需m天，其费用为f分；或者送到慢洗部，洗一块需n天(n>m)，其费用为s<f分。每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，...
02014年3月8日7,287费用流
「网络流24题」运输问题
题目描述 DescriptionW公司有m个仓库和n个零售商店。第i个仓库有ai个单位的货物；第j个零售商店需要bj个单位的货物。货物供需平衡，即 sum(si）=sum(bj)。从第i个仓库运送每单位货物到第j个零售商店的费用为cij。试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。编程任务：对于给定的m个仓库和n个零售商店间运送货物的费用，计算最优运输方案和最差运输方案。输入描述 InputDescription的第1行有2个...
02014年3月7日4,160费用流
「JoyOI1982」武器分配
描述Description后勤部队运来一批武器（机枪和盔甲）。你要把这些武器分配给手下的marine们（每人一部机枪，一套盔甲）。可是问题来了。。。这些武器的型号不相同（武器是由出价最低的承包商制造的），把一部m型的机枪和一套n型的盔甲分配给一个marine得到的不满意值为(m-n)^2（每个marine当然希望自己得到的武器是同一型号的）。你的任务就是把a部机枪和b套盔甲分配给手下n个marine。使他们的不满意值之和最小。输入格式InputF...
02014年2月25日3,045费用流
「BZOJ1877」[SDOI2009] 晨跑
DescriptionElaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天从寝室出发跑到学校，保证寝室编号为1，学校编号为N。Elaxia的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的...
22014年2月23日5,354费用流
「CODEVS1913」数字梯形问题
题目描述 Description给定一个由n行数字组成的数字梯形如下图所示。梯形的第一行有m个数字。从梯形的顶部的m个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。规则1：从梯形的顶至底的m条路径互不相交。规则2：从梯形的顶至底的m条路径仅在数字结点处相交。规则3：从梯形的顶至底的m条路径允许在数字结点相交或边相交。对于给定的数字梯形，分别按照规则1，规则2，和规则3计算出从梯形的顶至底...
02014年2月21日3,977费用流
「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,848费用流,最大流