luogu P2050 [NOI2012] 美食节

题意

CZ 市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。

作为一个喜欢尝鲜的美食客，小 M 自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小 M 仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小 M 开始研究起了做菜顺序的问题，即安排一个做菜的顺序使得同学们的等待时间最短。

小 M 发现，美食节共有 \(n\) 种不同的菜品。每次点餐，每个同学可以选择其中的一个菜品。总共有 \(m\) 个厨师来制作这些菜品。当所有的同学点餐结束后，菜品的制作任务就会分配给每个厨师。然后每个厨师就会同时开始做菜。厨师们会按照要求的顺序进行制作，并且每次只能制作一人份。

此外，小 M 还发现了另一件有意思的事情——虽然这 \(m\) 个厨师都会制作全部的 \(n\) 种菜品，但对于同一菜品，不同厨师的制作时间未必相同。他将菜品用 \(1, 2, \ldots, n\) 依次编号，厨师用 \(1, 2, \ldots, m\) 依次编号，将第 \(j\) 个厨师制作第 \(i\) 种菜品的时间记为 \(t_{i,j}\)。

小 M 认为：每个同学的等待时间为所有厨师开始做菜起，到自己那份菜品完成为止的时间总长度。换句话说，如果一个同学点的菜是某个厨师做的第 \(k\) 道菜，则他的等待时间就是这个厨师制作前 \(k\) 道菜的时间之和。而总等待时间为所有同学的等待时间之和。

现在，小 M 找到了所有同学的点菜信息——有 \(p_i\) 个同学点了第 \(i\) 种菜品（\(i=1, 2, \ldots, n\)）。他想知道的是最小的总等待时间是多少。

题解

这道题很厉害啊，是 P2053 [SCOI2007] 修车 的加强版。
这两题唯一的区别就是车的数量，先来解决建模问题。
我们可以想到每个人做出的贡献是前面等待时间的和，这个问题并不能好的解决。
我们可以想单独的一个人的贡献，一辆车在倒数第 \(j\) 个被修理，这次的贡献就是 \(j*T_{i,j}\)，所以我们将修车师傅拆为 \(n\) 个点，代表他修的 \(n\) 个阶段的车，同时由于多个工人可以同时修理不同的车，所以不用保证每个阶段只能有一辆车，但是一辆车只能修一次。
1.\(s\) 向工人的每个阶段连流 \(1\)，费 \(0\) 的边。
2.工人的倒数第 \(j\) 个阶段向车 \(i\) 连流 \(1\)，费 \(j*T{i,j}\)的边。
3.车向 \(t\)，连一条流 \(1\)，费 \(0\)的边。
这样做是对的，因为被走过的边一定是工人的一个前缀，这样做一定是优的。
这样就解决了这个弱化版，但是美食节这道题阶段数太多了。
如果像修车这样嗯拆就有 \(\sum p_im\) 个点，显然太多了。
感觉这个解决方法真的很牛逼。
和动态开点线段树类似，我们发现每种车对应的工人的阶段肯定是一段一段的。
然后接下来的思路就很神了，我们先将每个工人的第一个点拆出来，然后跑最大流。
如果一个工人的一个阶段被选了，则下面一个阶段也有可能被选，连边，跑最大流。
做到最后，发现有效的边都被连上了，无用的边最多只有 \(m\) 条。