「BZOJ2879」[NOI2012]美食节

Description

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

HINT

对于 $100\%$ 的数据， $n \leq 40, m \leq 100, p \leq 800, t_{i,j} \leq 1000($ 其中 $p = \sum p_i)$

Solution

force

就是「BZOJ1070」修车问题了

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 810*110, M = 3200000 * 3;

struct Edge {
    int u, v, nxt,f, w;
}e[M*2];
int head[N], en = 1;
void addedge(int x, int y, int z, int w) {
    e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = z, e[en].w = w;
    e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0, e[en].w = -w;
}
const int inf = 1e9;
int s, t;
int d[N], pre[N], inc[N];
bool inq[N];
bool spfa() {
    for(int i = 1; i <= t; ++i) d[i] = inf;
    d[s] = 0;
    inc[s] = inf;
    queue<int>q;
    q.push(s);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        inq[x] = 0;
        for(int i = head[x]; i;i = e[i].nxt) if(e[i].f && d[e[i].v] > d[x] + e[i].w) {
            d[e[i].v] = d[x] + e[i].w;
            pre[e[i].v] = i;
            inc[e[i].v] = min(inc[x], e[i].f);
            if(!inq[e[i].v]) inq[e[i].v] = 1, q.push(e[i].v);
        }
    }
    return d[t] < inf;
}
int KM() {
    int x = t;
    while(x != s) {
        e[pre[x]].f -= inc[t];
        e[pre[x] ^ 1].f += inc[t];
        x = e[pre[x]].u;        
    }
    return inc[t] * d[t];
}
int n, m, tot;
int id(int x, int y) {
    return (x - 1) * tot + y + n;
}
int a[N];
int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) {
        a[i] = read();
        tot += a[i];
    }
    s = m * tot + n + 1;
    t = m * tot + n + 2;
    for(int i = 1; i <= n; ++i)
        addedge(i, t, a[i], 0);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            int x = read();
            for(int k = 1; k <= tot; ++k)
                addedge(id(j, k), i, 1, x * k);
        }
    }
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= tot; ++j)
            addedge(s, id(i, j), 1, 0);
    int res = 0;
    while(spfa()) res += KM();
    printf("%d\n", res);
    return 0;
}

果然TLE了

std

考虑优化，如果第 $i$ 个厨师在做倒数第 $j$ 个菜，我们等第 $j-1$ 加入割边集的时候再添加这条边，也就是实现动态加边的过程。

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 810*110, M = 3200000 * 3;

struct Edge {
    int u, v, nxt,f, w;
}e[M*2];
int head[N], en = 1;
void addedge(int x, int y, int z, int w) {
    e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = z, e[en].w = w;
    e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0, e[en].w = -w;
}
const int inf = 1e9;
int s, t;
int d[N], pre[N], inc[N];
bool inq[N];
bool spfa() {
    for(int i = 1; i <= t; ++i) d[i] = inf;
    d[s] = 0;
    inc[s] = inf;
    queue<int>q;
    q.push(s);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        inq[x] = 0;
        for(int i = head[x]; i;i = e[i].nxt) if(e[i].f && d[e[i].v] > d[x] + e[i].w) {
            d[e[i].v] = d[x] + e[i].w;
            pre[e[i].v] = i;
            inc[e[i].v] = min(inc[x], e[i].f);
            if(!inq[e[i].v]) inq[e[i].v] = 1, q.push(e[i].v);
        }
    }
    return d[t] < inf;
}
bool vis[110][810];
int b[110][120];
int n, m, tot;
int id(int x, int y) {
    return (x - 1) * tot + y + n;
}
struct T {
    int x, y;
}c[110*810];
int KM() {
    int x = t;
    while(x != s) {
        if(x != s && x != t && x > n) {
            if(c[x].y < tot && !vis[c[x].x][c[x].y + 1]) {
                addedge(s, id(c[x].x, c[x].y + 1), 1, 0);
                for(int i = 1; i <= n; ++i) addedge(id(c[x].x, c[x].y + 1), i, 1, (c[x].y + 1) * b[c[x].x][i]);
                vis[c[x].x][c[x].y + 1] = 1;
            }
        }
        e[pre[x]].f -= inc[t];
        e[pre[x] ^ 1].f += inc[t];
        x = e[pre[x]].u;        
    }
    return inc[t] * d[t];
}
int a[N];
int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) {
        a[i] = read();
        tot += a[i];
    }
    s = m * tot + n + 1;
    t = m * tot + n + 2;
    for(int i = 1; i <= n; ++i)
        addedge(i, t, a[i], 0);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            b[j][i] = read();
            addedge(id(j, 1), i, 1, b[j][i]);
            vis[j][1] = 1;
        }
    }
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= tot; ++j) {
            int x = id(i, j);
            c[x].x = i;
            c[x].y = j;
        }
    for(int i = 1; i <= m; ++i) addedge(s, id(i, 1), 1, 0);
    int res = 0;
    while(spfa()) res += KM();
    printf("%d\n", res);
    return 0;
}