BZOJ 1070 [SCOI2007] 修车

发布于 2017-06-21  114 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1070

题意:m 个修车工,n 辆车,车一起来准备修,第 i 个人修 j 车的时间是 t[i][j],求最小平均等待时间...


几天不写费用流的板子都要忘了...

约定

一个形如 (i,j,x,y) 的四元组在此题解中表示建立一条从 i->j 流量为 x,费用为 y 的边

尝试去系统的考虑一下建模的过程:

首先考虑最终的目标结果是什么:n 辆车都被修完,总等待时间最小,对于这种 目标状态确定,答案与状态无关 的问题,可以尝试用一个确定的总流量去约束状态,通过费用流模型来获得决策过程中的最优解。

那么尝试去建立一个最小费用最大流的模型,显然最大流应该是 n 辆车的 n,建立源汇点,抽象 n 辆车作为节点,对于每辆车 i,是一定要修的,那么可以建立 (S,i,1,0),这样只要这 n 条为 1 的流都能流到汇点,则可以认为 n 辆车均完成了 修车 这一操作。

然后我们考虑如何累计费用,在整个过程中,我们可以选择什么 操作 呢?只有修车,尝试抽象这个过程,即:对于 i 车,是第 j 个人修的第 k 辆车所带来的费用。这是我们所需要累计的答案,通过网络流模型自调节得到最优解。显然, 修车的顺序 是具有影响的,那么我们可以对修车工人 拆点 ,对于工人 i,拆成 n 个点表示工人 j 修了第 k 辆车,显然建立 (每个拆后的点,T,1,0),这样如果我们将车点和工人点通过某种方式连接起来,最大流就一定可以跑出 n

考虑工人修车的费用是怎么带来的,首先假设我们已经知道每辆车都给哪个工人修,那么工人 i 修了一辆车 j 实际上就是让 j 车等待了 t[i][j],同时让后面排队的车也等待了 t[i][j]。所以,对于每个修车过程,对前面已经修完的车是没有影响的,我们只需要考虑后面的车,换句话说,如果我们知道一辆车是 倒数 第几辆修的,我们就可以轻易的累计出费用了。

所以我们之前的建模方案是不好的,我们转而考虑对于 i 车,是第 j 个人修的倒数第 k 辆车带来的费用,对于我们拆出的每个点,实际含义应当为第 j 个人修的第 k 辆车。 那么建立 (i, 拆后的点,1,k*t[i][j]) 即可!在实际的过程中,会尽可能的先跑倒数第一辆车,第二辆...

那么这道困扰了蒟蒻博主一段时间的大水题就做完啦

 


一个非常弱的准退役OIER