BZOJ1070修车

Mark_4396 · 2019-06-28 10:29:00 · 个人记录

对于”多人同时做多个任务“问题，巧妙拆点，将每个人拆成任务个数的点，每个点从前到后代表倒数第几个做任务，差分可知倒数第n天做的 任务需要的时间是tn n，总时间是t1+2t2+3t3+4t4+......+n*tn

思路：

假设我们现在只有一个修车师傅，共有A1,A2...AnA1,A2...AnA1,A2...An这n辆车，那么所有人的等待时间就分别为:

A1+A2...+An,A2+A3+..+An,...,An−1+An,AnA1+A2...+An,A2+A3+..+An,...,An-1+An,AnA1+A2...+An,A2+A3+..+An,...,An−1+An,An。 那所有人的等待时间呢？ 加起来，我们发现所有人的等待时间应该是:

A1∗n+A2∗(n−1)+...+AnA1n+A2(n-1)+...+AnA1∗n+A2∗(n−1)+...+An

那我们对每辆车被等待的时间考虑，发现越后修的被等待的时间越少

而且显而易见的，所有车被等待的时间即为所有人等待的时间 做法：

那我们从每辆车被等待的时间思考，思路也不是很难了，

将MMM位师傅拆成N∗MNMN∗M个点，第(i−1)∗N+j(i-1)N+j(i−1)∗N+j个点表示的是在修第jjj辆车的第iii位师傅，并将这个点连向每辆车，容量为111，边权为Cki∗jCki*jCki∗j（CijCijCij为第i辆车被第j位师傅修所花的时间,1<=k<=N1<=k<=N1<=k<=N），

然后再源点朝MMM个车点建边，N∗MN*MN∗M个师傅点朝汇点建边，都是边权为0，容量为1的边，最后跑最小费用最大流就行了。

同时建反向边应该不用我赘述了吧

注：本来是先修被等的时间越多，但是反过来仔细想先也没有什么问题

洛谷题解：https://www.luogu.org/problemnew/solution/P2053