[NOI2012] 美食节

题目描述

题目传送门

思路

考虑费用流。

首先费用提前计算，第 $j$ 个厨师倒数第 $k$ 个做第 $i$ 道菜的费用是 $k \times t_{i,j}$ ，因为最后的 $k$ 个人都需要等待这一道菜。

开始建图。

每道菜向源点连一条容量为 $p_i$ 费用为 $0$ 的边；
每个厨师拆成 $n$ 个点，向汇点连一条容量为 $1$ 费用为 $0$ 的点。
第 $i$ 道菜向第 $j$ 个初始所拆出来的第 $k$ 个点连一条容量为 $1$ 费用为 $k \times t_{i,j}$ 的边。

然后跑一次 MCMF。

这样子可以获得 $60$ 分的高分。

这里有一个 trick 叫做动态开点。

由于我们每次跑 SPFA 增广，只能找出一条增广路，所以我们可以暂时不连不需要的边。一开始我们将每个厨师拆成一个点进行连边，在遍历增广路的时候我们对每个厨师添加下一个点，并按照上述第 $3$ 个连边方式连边。

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10, MAXM = 4e7 + 10;
const int INF = 0x3f3f3f3f;

int N, M;

struct _ {
    int To, Next, Flow, Cost;
} G[MAXN];
int Head[MAXN], Cnt = 1;

void _add(int u, int v, int w, int c) {
    G[++Cnt] = {v, Head[u], w, c};
    Head[u] = Cnt;
}

void Add(int u, int v, int w, int c) {
    _add(u, v, w, c);
    _add(v, u, 0, -c);
}

int Dist[MAXN], Pre[MAXN], Incf[MAXN];
bool Vis[MAXN];
int T, S;

bool SPFA() {
    memset(Dist, 0x3f, sizeof Dist);
    queue<int> q;
    q.push(S);
    Vis[S] = true;
    Dist[S] = 0;
    Incf[S] = INF;
    Incf[T] = 0;
    while (q.size()) {
        int u = q.front();
        q.pop();
        Vis[u] = false;
        for (int i = Head[u]; i; i = G[i].Next) {
            const int &v = G[i].To, &w = G[i].Flow, &c = G[i].Cost;
            if (!w || Dist[v] <= Dist[u] + c) continue;
            Dist[v] = Dist[u] + c;
            Incf[v] = min(w, Incf[u]);
            Pre[v] = i;
            if (!Vis[v]) {
                q.push(v);
                Vis[v] = true;
            }
        }
    }
    return Incf[T];
}

int MaxFlow, MinCost;
int P[MAXN], A[50][150], CYB;

void UpDate() {
    MaxFlow += Incf[T];
    MinCost += Dist[T] * Incf[T];
    int x = T;
    while (x != S) {
        int i = Pre[x];
        G[i].Flow -= Incf[T];
        G[i ^ 1].Flow += Incf[T];
        x = G[i ^ 1].To;
    }
    x = G[Pre[T] ^ 1].To;
    P[++CYB] = P[x];
    Add(CYB, T, 1, 0);
    for (int i = Head[x]; i; i = G[i].Next) {
        int v = G[i].To, w = G[i ^ 1].Cost;
        if (v == T) continue;
        w += A[v][P[x]];
        Add(v, CYB, 1, w);
    }
}

void MCMF() {
    while (SPFA()) UpDate();
}

int main() {
    scanf("%d %d", &N, &M);
    S = 0, T = CYB = N + M + 1;
    for (int i = 1, x; i <= N; i++) {
        scanf("%d", &x);
        Add(S, i, x, 0);
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%d", &A[i][j]);
            Add(i, N + j, 1, A[i][j]);
        }
    }
    for (int i = 1; i <= M; i++) {
        Add(N + i, T, 1, 0);
        P[N + i] = i;
    }
    MCMF();
    cout << MinCost << endl;
}