bzoj 4108 [Wf2015]Catering

Description

有一家装备出租公司收到了按照时间顺序排列的n个请求.

这家公司有k个搬运工.每个搬运工可以搬着一套装备按时间顺序去满足一些请求.一个搬运工从第i个请求的位置把东西搬到第j个请求的位置需要一些费用.公司的编号是1,请求的编号是2到n+1.所有搬运工必需从公司出发.
求满足所有请求所需的最小搬运费用.

Input

有可能有多组数据(我也不知道).

第一行两个正整数n,k.
接下来n行,第i行有n-i+1个数.第j个数表示把装备从i搬到i+j的花费.

Output

输出一行一个整数表示最小花费.

Sample Input

1 1

10

Sample Output

10

HINT

n, k <= 100;

花费 <= 1,000,000

题解

将2-n+1拆点xi,yi
s->1,[0,k],0
1->xi,[0,inf],0
yi->t,[0,inf],0
xi->yi,[1,1],0
对于给出的费用，若i->j的费用为c
yi->xj,[0,inf],c

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define N 30010
#define inf 0x33333333
using namespace std;
typedef pair<int, int> Pair;
struct MFMC {
    struct node {
        int from, to, next, flow, cost;
    }e[N];
    int tot, st[N], pe[N], pv[N], dis[N], vis[N];
    void init() {
        tot = -1, memset(e, -1, sizeof e);
        memset(st, -1, sizeof st);
    }
    void add(int x, int y, int z, int zz) {
        e[++tot].to = y, e[tot].from = x;
        e[tot].flow = z, e[tot].cost = zz;
        e[tot].next = st[x], st[x] = tot;
    }
    void add_edge(int x, int y, int z, int zz) {
        add(x, y, z, zz), add(y, x, 0, -zz);
    }
    queue <int> que;
    bool spfa(int S, int T) {
        memset(dis, 0x33, sizeof dis);
        memset(vis, 0, sizeof vis);
        que.push(S), vis[S] = 1, dis[S] = 0;
        while(!que.empty()) {
            int now = que.front();
            que.pop();
            vis[now] = 0;
            for (int i = st[now]; ~i; i = e[i].next)
                if (e[i].flow > 0 && dis[e[i].to] > dis[now] + e[i].cost) {
                    dis[e[i].to] = dis[now] + e[i].cost;
                    pe[e[i].to] = i, pv[e[i].to] = now;
                    if (!vis[e[i].to])
                        vis[e[i].to] = 1, que.push(e[i].to);
                }
        }
        return dis[T] < inf;
    }
    Pair mfmc(int S, int T) {
        int COST = 0, FLOW = 0, flow;
        while(spfa(S, T)) {
            flow = inf;
            for (int i = T; i != S; i = pv[i])
                flow = min(flow, e[pe[i]].flow);
            COST += flow * dis[T];
            FLOW += flow;
            for (int i = T; i != S; i = pv[i])
                e[pe[i]].flow -= flow, e[pe[i] ^ 1].flow += flow;
        }
        return make_pair(FLOW, COST);
    }
}mcmf;
int n, m, x, y, z, k, d[N];
int main() {
    int S, T, s, t;
    mcmf.init();
    scanf("%d%d", &n, &k);
    s = 1, t = n * 2 + 3, S = t + 1, T = S + 1;
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n + 1; ++j)
            scanf("%d", &x), mcmf.add_edge(i + n + 1, j, inf, x);
    mcmf.add_edge(s, 1 + n + 1, k, 0);
    for (int i = 2; i <= n + 1; ++i)
        d[i]--, d[n + i + 1]++,
        mcmf.add_edge(n + 1 + i, t, inf, 0);
    for (int i = 1; i <= t; ++i)
        if (d[i] > 0)
            mcmf.add_edge(S, i, d[i], 0);
        else if (d[i] < 0)
            mcmf.add_edge(i, T, -d[i], 0);
    mcmf.add_edge(t, s, inf, 0);
    Pair ans = mcmf.mfmc(S, T);
    printf("%d\n", ans.second);
}