BZOJ 2879 [Noi2012]美食节 | 费用流 动态开点

时间：2023-11-11 16:10:44

这道题就是“修车”的数据加强版……但是数据范围扩大了好多，应对方法是“动态开点”。

首先先把“所有厨师做的倒数第一道菜”和所有菜连边，然后跑一下spfa，找出哪一个厨师在增广路上，把“这个厨师做的倒数第二道菜”和所有菜连边，然后继续spfa，如此循环往复直到spfa找不出最短路。

#include <queue>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <iostream>

#define space putchar(' ')

#define enter putchar('\n')

typedef long long ll;

using namespace std;

template <class T>

void read(T &x){

    char c;

    bool op = 0;

    while(c = getchar(), c < '0' || c > '9')

        if(c == '-') op = 1;

    x = c - '0';

    while(c = getchar(), c >= '0' && c <= '9')

        x = x * 10 + c - '0';

    if(op) x = -x;

}

template <class T>

void write(T x){

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar('0' + x % 10);

}

const int N = 100005, M = 10000005, INF = 0x3f3f3f3f;

int n, m, src, des, tot, ans, sum;

int cook[105][805], dish[805], id[N], rnk[N], w[45][105], p[45];

int ecnt = 1, adj[N], dis[N], pre[N], nxt[M], go[M], cap[M], cost[M];

void _add(int u, int v, int w, int c){

    go[++ecnt] = v;

    nxt[ecnt] = adj[u];

    adj[u] = ecnt;

    cap[ecnt] = w;

    cost[ecnt] = c;

}

void add(int u, int v, int w, int c){

    _add(u, v, w, c);

    _add(v, u, 0, -c);

}

bool spfa(){

    queue <int> que;

    static bool inq[N] = {0};

    for(int i = 1; i <= tot; i++)

        dis[i] = INF, pre[i] = 0;

    dis[src] = 0, que.push(src), inq[src] = 1;

    while(!que.empty()){

        int u = que.front();

        que.pop(), inq[u] = 0;

        for(int e = adj[u], v; e; e = nxt[e]){

            if(cap[e] && dis[u] + cost[e] < dis[v = go[e]]){

                dis[v] = dis[u] + cost[e], pre[v] = e;

                if(!inq[v]) que.push(v), inq[v] = 1;

            }

        }

    }

    return dis[des] < INF;

}

int main(){

    read(n), read(m);

    src = ++tot, des = ++tot;

    for(int i = 1; i <= n; i++)

        read(p[i]), sum += p[i];

    for(int i = 1; i <= n; i++)

        for(int j = 1; j <= m; j++)

            read(w[i][j]);

    for(int i = 1; i <= n; i++){

        dish[i] = ++tot, id[tot] = i;

        add(src, dish[i], p[i], 0);

    }

    for(int i = 1; i <= m; i++){

        cook[i][1] = ++tot, id[tot] = i, rnk[tot] = 1;

        add(cook[i][1], des, 1, 0);

        for(int j = 1; j <= n; j++)

            add(dish[j], cook[i][1], 1, w[j][i]);

    }

    while(spfa()){

        int tmp = go[pre[des] ^ 1], _cook = id[tmp], _rank = rnk[tmp], flow = INF;

        for(int e = pre[des]; e; e = pre[go[e ^ 1]])

            flow = min(flow, cap[e]);

        for(int e = pre[des]; e; e = pre[go[e ^ 1]])

            cap[e] -= flow, cap[e ^ 1] += flow;

        ans += flow * dis[des];

        cook[_cook][_rank + 1] = ++tot, id[tot] = _cook, rnk[tot] = _rank + 1;

        add(tot, des, 1, 0);

        for(int i = 1; i <= n; i++)

            add(dish[i], tot, 1, w[i][_cook] * (_rank + 1));

    }

    write(ans), enter;

    return 0;

}

相关文章