• https://www.luogu.com.cn/problem/P2050

用 上一题 的做法可以拿 60 分，考虑优化。我们发现对于每个厨师，它所被利用的边一定是一组前缀，因此可以贪心每进行一次增广后再动态加入新的边。

#include <lastweapon/io>
#include <lastweapon/mincostflow>
using namespace lastweapon;

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    int n, m, p; RD(n, m); p = 800; int s = n+m*p, t = s+1, nn = 0;
    mcf_graph<int, int> G(t+1);

    REP(i, n) G.add_edge(s, i, RD(), 0);
    REP(i, p) REP(j, m) G.add_edge(n+p*j+i, t, 1, 0);

    REP(i, n) REP(j, m) {
        int c; RD(c); REP(k, p) G.add_edge(i, n+p*j+k, 1, (k+1)*c);
    }

    printf("%d\n", G.flow(s, t).se);
}

Posted by xiaodao
Category: 日常