题目地址：洛谷：【P2050】[NOI2012]美食节 – 洛谷、BZOJ：Problem 2879. — [Noi2012]美食节

题目描述

CZ市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。作为一个喜欢尝鲜的美食客，小M自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小M仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小M开始研究起了做菜顺序的问题，即安排一个做菜的顺序使得同学们的等待时间最短。小M发现，美食节共有n种不同的菜品。每次点餐，每个同学可以选择其中的一个菜品。总共有m个厨师来制作这些菜品。当所有的同学点餐结束后，菜品的制作任务就会分配给每个厨师。然后每个厨师就会同时开始做菜。厨师们会按照要求的顺序进行制作，并且每次只能制作一人份。此外，小M还发现了另一件有意思的事情: 虽然这m个厨师都会制作全部的n种菜品，但对于同一菜品，不同厨师的制作时间未必相同。他将菜品用1, 2, …, n依次编号，厨师用1, 2, …, m依次编号，将第j个厨师制作第i种菜品的时间记为 ti,j 。小M认为：每个同学的等待时间为所有厨师开始做菜起，到自己那份菜品完成为止的时间总长度。换句话说，如果一个同学点的菜是某个厨师做的第k道菜，则他的等待时间就是这个厨师制作前k道菜的时间之和。而总等待时间为所有同学的等待时间之和。现在，小M找到了所有同学的点菜信息: 有 pi 个同学点了第i种菜品（i=1, 2, …, n）。他想知道的是最小的总等待时间是多少。

输入输出格式

输入格式：
输入文件的第1行包含两个正整数n和m，表示菜品的种数和厨师的数量。 第2行包含n个正整数，其中第i个数为pi，表示点第i种菜品的人数。 接下来有n行，每行包含m个非负整数，这n行中的第i行的第j个数为ti,j，表示第j个厨师制作第i种菜品所需的时间。 输入文件中每行相邻的两个数之间均由一个空格隔开，行末均没有多余空格。

输出格式：
输出仅一行包含一个整数，为总等待时间的最小值。

输入输出样例

输入样例#1：

3 2 
3 1 1 
5 7 
3 6 
8 9

输出样例#1：

47

说明

厨师1先制作1份菜品2，再制作2份菜品1。点这3道菜的3个同学的等待时间分别为3，3+5=8，3+5+5=13。
厨师2先制作1份菜品1，再制作1份菜品3。点这2道菜的2个同学的等待时间分别为7，7+9=16。
总等待时间为3+8+13+7+16=47。
虽然菜品1和菜品3由厨师1制作更快，如果这些菜品都由厨师1制作，总等待时间反而更长。如果按上述的做法，将1份菜品1和1份菜品3调整到厨师2制作，这样厨师2不会闲着，总等待时间更短。
可以证明，没有更优的点餐方案。
对于100%的数据，n <= 40, m <= 100, p <= 800, ti,j <= 1000 （其中p = ∑pi）

题解

首先你得把这个题写了：[SCOI2007]修车 题解 | KSkun’s Blog。
其实看一下这个题跟修车这个题是一模一样的，只是在这里，每种食物对应的点向汇的连边的容量是食物的需求数量pi。简单地说，就是按照倒序来加每个厨师的菜，对于第i个厨师的倒数第j道菜，它对答案的贡献是t[菜][i]*j，对每个厨师的每道菜建点，以此为费用连边跑MCMF即可。
我们考虑一下这个题的边的数量，全建出来是nmp+mp+n规模的，稍微有点多，这个题又有点卡常，所以我们可以采取动态加边的策略。我们先把每个厨师的倒数第1道菜的边全连上，每条最短增广路对应的是一个厨师的一道菜被确定了，因此此时就可以对这个厨师的下一道菜连边，这样可以有效地减少边的数量，避免TLE。
具体的实现方法可以参见代码。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, cost, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap, int cost) {
    gra[tot] = Edge {v, cap, cost, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, -cost, head[v]}; head[v] = tot++;
}

int n, m, k;

int dis[MAXN], f[MAXN], pre[MAXN], pree[MAXN];
std::queue<int> que;
bool inque[MAXN];

inline bool spfa(int s, int t) {
    memset(dis, 0x3f, sizeof(dis));
    memset(f, 0, sizeof(f));
    dis[s] = 0; f[s] = INF; inque[s] = true; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop(); inque[u] = false;
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap > 0 && dis[v] > dis[u] + gra[i].cost) {
                dis[v] = dis[u] + gra[i].cost;
                f[v] = std::min(gra[i].cap, f[u]);
                pre[v] = u; pree[v] = i;
                if(!inque[v]) {
                    inque[v] = true; que.push(v);
                }
            }
        }
    }
    return f[t] != 0;
}

int p[105], t[105][105], sum, S, T;
int flow, cost;

inline void mcmf(int s, int t) {
    while(spfa(s, t)) {
        int p;
        for(int i = t; i != s; i = pre[i]) {
            gra[pree[i]].cap -= f[t];
            gra[pree[i] ^ 1].cap += f[t];
            if(pre[i] == s) p = i;
        }
        flow += f[t]; cost += dis[t] * f[t];
        int cook = p / sum + 1, dish = p % sum + 1;
        if(dish <= 1) continue;
        addedge(s, (cook - 1) * sum + dish, 1, 0);
        for(int i = 1; i <= n; i++) {
            addedge((cook - 1) * sum + dish, i + m * sum, 1, ::t[i][cook] * dish);
        }
    }
}

// 1 ~ m*sum cook
// (i-1)*sum+j ith cook jth dish
// m*sum+1 ~ m*sum+n dish
// Feel headache to so many vertexs
int main() {
    memset(head, -1, sizeof(head));
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        p[i] = readint();
        sum += p[i];
    }
    S = m * sum + n + 1; T = S + 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            t[i][j] = readint();
        }
    }
    for(int i = 1; i <= n; i++) {
        addedge(i + m * sum, T, p[i], 0);
    }
    for(int i = 1; i <= m; i++) {
        addedge(S, (i - 1) * sum + 1, 1, 0);
        for(int j = 1; j <= n; j++) {
            addedge((i - 1) * sum + 1, j + m * sum, 1, t[j][i]);
        }
    }
    mcmf(S, T);
    printf("%d", cost);
    return 0;
}