标签 - 费用流

? 解题记录 ? ? BZOJ ? ? 费用流 ? ? 网络流 ?    2018-10-01 10:03:10    495    0    0
很套路的一道题,做过无限之环来看这道题还是十分好想的因为我比较菜,考试的时候就没能想出来。按照套路,把格子黑白染色,然后考虑图的特点,到一个地方一定拐弯。并且,对于一条回路来说,正向和反向的贡献都是一样的。接下来,我们指定黑、白格子的流向,考虑一个白格子的流出一定是某个黑格子的流入。那么就好办了,我们规定黑格子横进竖出,白格子横出竖进。这样我们把问题抽象成一张图,对于每一个格子可以选择从进向自己连边,自己向出连边,相当于每种进的方案都可以选择两种出去的方案。但是题目还有一个隐含条件,一个点只能经过一条流量,也就是出入度都是1,想到限制出入度便想到了最小路劲覆盖的模型。于是,初步的构图便完成了。
? 解题记录 ? ? BZOJ ? ? 网络流 ? ? 费用流 ?    2018-08-13 10:51:41    286    0    0
【题目描述】同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。 说明:顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。 【输入】第一行有两个m,n,表示技术人员数与顾客数。 接下来n行,每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。 【输出】最小平均等待时间,答案精确到小数点后2位。 【输入样例】2 2 3 2 1 4 【输出样例】1.50 【提示】数据范围: (2<
? 解题记录 ? ? 洛谷 ? ? 费用流 ? ? 网络流 ?    2018-03-28 09:19:52    534    0    0
题目描述申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题:为即将启动的奥运新项目招募一批短期志愿者。经过估算,这个项目需要N 天才能完成,其中第i 天至少需要Ai 个人。 布布通过了解得知,一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天,招募费用是每人Ci 元。新官上任三把火,为了出色地完成自己的工作,布布希望用尽量少的费用招募足够的志愿者,但这并不是他的特长!于是布布找到了你,希望你帮他设计一种最优的招募方案。 输入输出格式输入格式:   第一行包含两个整数N, M,表示完成项目的天数和可以招募的志愿者的种
? 解题记录 ? ? 洛谷 ? ? 费用流 ? ? 网络流 ?    2018-01-28 10:38:55    517    0    0
题目描述给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大 输入输出格式输入格式:   第一行两个数n,k(1<=n<=50, 0<=k<=10) 接下来n行,每行n个数,分别表示矩阵的每个格子的数   输出格式:   一个数,为最大和   输入输出样例输入样例#1: 复制3 1 1 2 3 0 
? 解题记录 ? ? 洛谷 ? ? 费用流 ? ? 网络流 ?    2018-01-27 23:29:45    381    0    0
题目描述火星探险队的登陆舱将在火星表面着陆,登陆舱内有多部障碍物探测车。登陆舱着陆后,探测车将离开登陆舱向先期到达的传送器方向移动。探测车在移动中还必须采集岩石标本。每一块岩石标本由最先遇到它的探测车完成采集。每块岩石标本只能被采集一次。岩石标本被采集后,其他探测车可以从原来岩石标本所在处通过。探测车不能通过有障碍的地面。本题限定探测车只能从登陆处沿着向南或向东的方向朝传送器移动,而且多个探测车可以在同一时间占据同一位置。如果某个探测车在到达传送器以前不能继续前进,则该车所采集的岩石标本将全部损失。 用一个 P·Q 网格表示登陆舱与传送器之间的位置。登陆舱的位置在(X1,Y1)处,传送器 的位