• 「网络流24题」航空计划

    「网络流24题」航空计划

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

    12014年4月3日1,688费用流
  • 「BZOJ3171」[TJOI2013] 循环格

    「BZOJ3171」[TJOI2013] 循环格

    DescriptionInput第一行两个整数R,C。表示行和列,接下来R行,每行C个字符LRUD,表示左右上下。Output一个整数,表示最少需要修改多少个元素使得给定的循环格完美SampleInput34RRRDURLLLRRRSampleOutput2HINT1<=R,L<=15题解可知每个点的出度=入度=1二分图+费用流S向每个点连容量1费用0的边每个点拆出的点向T连容量1,费用0的边每个格子向四周连费用0或1的边[crayon-5b519cd05d78a145044...

    02014年3月18日2,574费用流
  • 「BZOJ2424」[HAOI2010] 订货

    「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日2,571费用流
  • 「BZOJ1221」[HNOI2001] 软件开发

    「BZOJ1221」[HNOI2001] 软件开发

    Description某软件公司正在规划一项n天的软件开发计划,根据开发计划第i天需要ni个软件开发人员,为了提高软件开发人员的效率,公司给软件人员提供了很多的服务,其中一项服务就是要为每个开发人员每天提供一块消毒毛巾,这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种,A种方式的消毒需要a天时间,B种方式的消毒需要b天(b>a),A种消毒方式的费用为每块毛巾fA,B种消毒方式的费用为每块毛巾fB,而买...

    02014年3月16日2,051费用流
  • 「网络流24题」分配问题

    「网络流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日2,541费用流
  • 「网络流24题」负载平衡问题

    「网络流24题」负载平衡问题

    题目描述 DescriptionG公司有n个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使n个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。«编程任务:对于给定的n个环形排列的仓库的库存量,编程计算使n个仓库的库存数量相同的最少搬运量。输入描述 InputDescription第1行中有1个正整数n(n<=100),表示有n个仓库。第2行中有n个正整数,表示n个仓库的库存量。输出描述 Outpu...

    02014年3月11日2,553费用流
  • 「网络流24题」餐巾计划问题

    「网络流24题」餐巾计划问题

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

    02014年3月8日4,572费用流
  • 「网络流24题」运输问题

    「网络流24题」运输问题

    题目描述 DescriptionW公司有m个仓库和n个零售商店。第i个仓库有ai个单位的货物;第j个零售商店需要bj个单位的货物。货物供需平衡,即 sum(si)=sum(bj)。从第i个仓库运送每单位货物到第j个零售商店的费用为cij。试设计一个将仓库中所有货物运送到零售商店的运输方案,使总运输费用最少。编程任务:对于给定的m个仓库和n个零售商店间运送货物的费用,计算最优运输方案和最差运输方案。输入描述 InputDescription的第1行有2个...

    02014年3月7日2,164费用流
  • 「JoyOI1982」武器分配

    「JoyOI1982」武器分配

    描述Description后勤部队运来一批武器(机枪和盔甲)。你要把这些武器分配给手下的marine们(每人一部机枪,一套盔甲)。可是问题来了。。。这些武器的型号不相同(武器是由出价最低的承包商制造的),把一部m型的机枪和一套n型的盔甲分配给一个marine得到的不满意值为(m-n)^2(每个marine当然希望自己得到的武器是同一型号的)。你的任务就是把a部机枪和b套盔甲分配给手下n个marine。使他们的不满意值之和最小。输入格式InputF...

    12014年2月25日1,814费用流
  • 「BZOJ1877」[SDOI2009] 晨跑

    「BZOJ1877」[SDOI2009] 晨跑

    DescriptionElaxia最近迷恋上了空手道,他为自己设定了一套健身计划,比如俯卧撑、仰卧起坐等等,不过到目前为止,他坚持下来的只有晨跑。现在给出一张学校附近的地图,这张地图中包含N个十字路口和M条街道,Elaxia只能从一个十字路口跑向另外一个十字路口,街道之间只在十字路口处相交。Elaxia每天从寝室出发跑到学校,保证寝室编号为1,学校编号为N。Elaxia的晨跑计划是按周期(包含若干天)进行的,由于他不喜欢走重复的...

    22014年2月23日3,104费用流
  • 「CODEVS1913」数字梯形问题

    「CODEVS1913」数字梯形问题

    题目描述 Description给定一个由n行数字组成的数字梯形如下图所示。梯形的第一行有m个数字。从梯形的顶部的m个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。规则1:从梯形的顶至底的m条路径互不相交。规则2:从梯形的顶至底的m条路径仅在数字结点处相交。规则3:从梯形的顶至底的m条路径允许在数字结点相交或边相交。对于给定的数字梯形,分别按照规则1,规则2,和规则3计算出从梯形的顶至底...

    02014年2月21日1,924费用流
  • 「BZOJ1834」[ZJOI2010] network 网络扩容

    「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日4,662费用流,最大流