bzoj2879: [Noi2012]美食节 | jeffswt: the ac moments

Description

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\) 种菜品 (\(1 \leq i \leq n\)) . 他想知道的是最小的总等待时间是多少.

Input

输入文件的第 \(1\) 行包含两个正整数 \(n\) 和 \(m\), 表示菜品的种数和厨师的数量.

第 \(2\) 行包含 \(n\) 个正整数, 其中第 \(i\) 个数为 \(p_i\), 表示点第 \(i\) 种菜品的人数.

接下来有 \(n\) 行, 每行包含 \(m\) 个非负整数, 这 \(n\) 行中的第 \(i\) 行的第 \(j\) 个数为 \(t_{i,j}\), 表示第 \(j\) 个厨师制作第 \(i\) 种菜品所需的时间.

输入文件中每行相邻的两个数之间均由一个空格隔开, 行末均没有多余空格.

Output

输出仅一行包含一个整数, 为总等待时间的最小值.

Sample Input

Sample Output

Data Range

对于 100% 的数据,\(n \leq 40, m \leq 100, p \leq 800, t_{i,j} \leq 1000\), (其中 \(p = \sum p_i\), 即点菜同学的总人数).

每组数据的 \(n, m, p\) 值如下:

ID	\(n\)	\(m\)	\(p\)
\(1\)	\(5\)	\(5\)	\(10\)
\(2\)	\(40\)	\(1\)	\(400\)
\(3\)	\(40\)	\(2\)	\(300\)
\(4\)	\(40\)	\(40\)	\(40\)
\(5\)	\(5\)	\(40\)	\(100\)
\(6\)	\(10\)	\(50\)	\(200\)
\(7\)	\(20\)	\(60\)	\(400\)
\(8\)	\(40\)	\(80\)	\(600\)
\(9\)	\(40\)	\(100\)	\(800\)
\(10\)	\(40\)	\(100\)	\(800\)

Explanation

对于打算要正解分的人给他骗分算法他也不看, 不打算全要分的人给他正解也不看, 就是这么套路==

现在想这个问题, 没有做过 SCOI2007 修车 (bzoj1070, 无传送门) 的请出门右转先去做那道题, 不然这道没法做 QwQ

会了那道题这道题还是做不出来 QwQ

其实是动态加边, 因为之前有些边根本用不上, 还在 SPFA 里面白跑吃时间......

但是动态加边有技巧, 比如我看了一种 (hzwer) 很正常的动态加边, 而且很好理解, 并且十分的 OOP, 但是以我的巨大常数写出来就是个噩梦~

开了 -O2 用了 STL 队列比 hzwer 慢一倍, 用了自己写的队列还是比他慢上 10% 左右, 而且还是在开优化的情况下, 这样明显交不过, 魔改了好几次以后无限 TLE, 终于失去了信心.

后来发现另外一种动态加边的方式: 他把源汇的方向反过来 (这样似乎可以减小搜索深度, 所以虽然复杂度一样但是实际是要快上四倍左右的), 然后就是一些奇怪的加边方法, 不明觉厉.

讲真我的代码里为了更 OOP 写上 callback(...) 这类的函数真的好吗=n=

还是需要思考一下的. 如果想用哪种更慢的方式, 就把 #define USE_FAST_APPROACH 注释掉, 然后加上一行 #define USE_GENERAL_APPROACH 就可以了 (我觉得诸位大神应该能看懂吧 orz)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

#define SWTAPI inline
#define USE_FAST_APPROACH
using namespace std;
typedef long long lli;
const int maxn = 100100, maxm = 3000100, maxN = 110;
const lli infinit = 0x3f3f3f3f;

inline lli read(void)
{
    lli x = 0, f = 1; char ch=getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

template <typename _Type>
class fast_queue
{
public:
    _Type arr[maxn];
    int beg, end;
    SWTAPI _Type front(void) {
        return arr[beg]; }
    SWTAPI void push(const _Type& val) {
        arr[end++] = val;
        if (end >= maxn) end = 0;
        return ; }
    SWTAPI void pop(void) {
        beg += 1;
        if (beg >= maxn) beg = 0;
        return ; }
    SWTAPI bool empty(void) {
        return beg == end; }
    fast_queue(void) {
        beg = end = 0;
        return ;
    }
};

class SpfaMaxFlow
{
public:
    struct edge
    {
        int u, v;
        lli flow, cost;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], *from[maxn], epool[maxm];
    SWTAPI void add_edge(int u, int v, lli flow, lli cost)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow; p->cost = cost;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0; q->cost = -cost;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool inque[maxn];
    lli dist[maxn];
    SWTAPI bool bfs(void)
    {
        for (int i = 0; i <= n; i++)
            dist[i] = infinit, inque[i] = false, from[i] = NULL;
        static fast_queue<int> que;
        que.push(s);
        inque[s] = true;
        dist[s] = 0;
        // Emulating a queue, manually
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && dist[p] + ep->cost < dist[ep->v]) {
                    dist[ep->v] = dist[p] + ep->cost;
                    if (!inque[ep->v]) {
                        que.push(ep->v);
                        inque[ep->v] = true;
                    }
                    from[ep->v] = ep;
                }
            inque[p] = false;
        }
        if (dist[t] < infinit)
            return true;
        return false;
    }
    SWTAPI lli spfa(void(&callback)(int))
    {
        lli res = 0;
        while (bfs()) {
            lli flow = infinit;
            int targ = 0;
            for (edge *ep = from[t]; ep; ep = from[ep->u]) {
                flow = min(flow, ep->flow);
                if (!ep->u) targ = ep->v;
            }
            for (edge *ep = from[t]; ep; ep = from[ep->u]) {
                ep->flow -= flow;
                ep->rev->flow += flow;
            }
            res += dist[t] * flow;
            callback(targ);
        }
        return res;
    }
} graph;

int m, n;
lli c[maxN], C, t[maxN][maxN];
int num[maxN], pos[maxN];

SWTAPI void build_dynamic(int y)
{
    #ifdef USE_GENERAL_APPROACH
    int a = (y-1) / C + 1,
        b = y % C + 1;
    for (int i = 1; i <= m; i++)
        graph.add_edge((a-1)*C+b, n*C+i, 1, b*t[i][a]);
    #endif
    #ifdef USE_FAST_APPROACH
    static int tot = m+n;
    int j = 1;
    for (; j <= n && graph.epool[pos[j]].flow <= 0; j++);
    num[j] += 1, tot += 1;
    graph.add_edge(tot, graph.t, 1, 0);
    pos[j] = graph.ecnt;
    for (int i = 1; i <= m; i++)
        graph.add_edge(i, tot, 1, num[j] * t[i][j]);
    #endif
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d%d", &m, &n);
    C = 0;
    for (int i = 1; i <= m; i++) {
        c[i] = read();
        C += c[i];
    }
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            t[i][j] = read();
    // Creating graph (static part)
    #ifdef USE_GENERAL_APPROACH
    graph.n = n*C + m + 1;
    graph.s = 0;
    graph.t = graph.n;
    for (int i = 1; i <= n*C; i++)
        graph.add_edge(graph.s, i, 1, 0);
    for (int i = 1; i <= m; i++)
        graph.add_edge(n*C + i, graph.t, c[i], 0);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            graph.add_edge((i-1)*C+1, n*C+j, 1, t[j][i]);
    #endif
    #ifdef USE_FAST_APPROACH
    graph.n = m+n+C+2;
    graph.s = graph.n - 1;
    graph.t = graph.n;
    for (int i = 1; i <= m; i++)
        graph.add_edge(graph.s, i, c[i], 0);
    for (int j = 1; j <= n; j++) {
        graph.add_edge(m+j, graph.t, 1, 0);
        num[j] = 1, pos[j] = graph.ecnt;
        for (int i = 1; i <= m; i++)
            graph.add_edge(i, m+j, 1, t[i][j]);
    }
    #endif
    // Running maximum flow and dynamically creating edges
    lli res = graph.spfa(build_dynamic);
    // Retrieved result
    printf("%lld\n", res);
    return 0;
}