hzwer.com _ Home | http://hzwer.com

« 上一页下一页 »Current position : 首页 >> 图论 >> 第27页

• 「网络流24题」圆桌聚餐

  

  «问题描述： 假设有来自m个不同单位的代表参加一次国际会议。每个单位的代表数分别为 ri(i=1,2,3...m),。会议餐厅共有n张餐桌，每张餐桌可容纳ci(i=1,2...n)个代表就餐。 为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法， 给出满足要求的代表就餐方案。 «编程任务： 对于给定的代表数和餐桌数以及餐桌容量，编程计算满足要求的代表就餐方案。 «数据输入...
  32014年3月8日5,307最大流

• 「网络流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二分法,最大流,广度搜索

• 「BZOJ2330」[SCOI2011] 糖果

  

  Description 幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。 Input输入的第一行是两...
  22014年3月5日8,850差分约束

• 「CODEVS1222」信与信封问题

  

  题目描述 DescriptionJohn先生晚上写了n封信，并相应地写了n个信封将信装好，准备寄出。但是，第二天John的儿子Small John将这n封信都拿出了信封。不幸的是，Small John无法将拿出的信正确地装回信封中了。 将Small John所提供的n封信依次编号为1，2，…，n；且n个信封也依次编号为1，2，…，n。假定Small John能提供一组信息：第i封信肯定不是装在信封j中。请编程帮助Small John，尽可能多地将信正确地装...
  02014年3月2日4,869二分图匹配

• 「JoyOI1467」通向聚会的道路

  

  背景BackgroundCandy住在一个被划分为n个区域的神奇小镇中，其中Candy的家在编号为n的区域，Candy生日这天，大家都急急忙忙赶去Candy家庆祝Candy的生日。描述DescriptionCandy共有t个朋友住在不同的区域。小镇有m条道路，小镇的神奇之处在于其中的p1条道路只会在你走过区域的的个数为奇数时候开启，p2道路只会在你走过区域的个数为偶数的时候开启，剩下的道路一直都会开启。并且，所有的道路只能够单向通过。飘飘乎居士希望...
  02014年3月2日4,611spfa

• 「BZOJ1614」[Usaco2007 Jan] Telephone Lines架设电话线

  

  题目描述FarmerJohn打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。   FJ的农场周围分布着N(1<=N<=1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1<=P<=10,000)对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。    第i对电话线杆的两个端点分别为A_i、B_i，它们间的距离为L...
  32014年3月1日6,387spfa,二分法

• 「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最小割

• 「POJ3255」Roadblocks

  

  DescriptionBessiehasmovedtoasmallfarmandsometimesenjoysreturningtovisitoneofherbestfriends.Shedoesnotwanttogettoheroldhometooquickly,becauseshelikesthesceneryalongtheway.Shehasdecidedtotakethesecond-shortestratherthantheshortestpath.Sheknowstheremustbesomesecond-shortestpath.Thecountrysideconsistsof R (1≤ R ≤100,000)bidirectionalroads,eachlinkingtwooftheN(1≤ N ≤5000)intersectio...
  02014年2月27日2,830spfa

• 「JoyOI1982」武器分配

  

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