P2754 [CTSC1999] 家园 / 星际转移问题题解

开始时,将源点连一条权值为 \(k\) 的边到地球。

然后以时间分层，从上一层的点连接到下一层的点，权值为飞船载人数量，并将代表月球的点连接到汇点。每加一层，在上一层的基础上进行增广，看能不能增加流量，如果流量变为 \(k\)，那么证明运送完成。

可以证明枚举时间最多到 \(1500\)，图的点数不超过 \(22500\)，边数越大越好。

不用担心超时，luogu上最慢才 31 ms

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 22500, M = 10000010, INF = 0x3f3f3f3f3f3f3f3f;

struct edge {
    int to, next, w;
} e[M];

int head[N], idx = 1;

void add(int u, int v, int w) {
    idx++, e[idx].to = v, e[idx].next = head[u], e[idx].w = w, head[u] = idx;
    idx++, e[idx].to = u, e[idx].next = head[v], e[idx].w = 0, head[v] = idx;
}

int S, T;
int dep[N];

bool bfs() {
    queue<int> q;
    q.push(S);
    memset(dep, 0x3f, sizeof(dep));
    dep[S] = 1;
    while (q.size()) {
        int t = q.front();
        q.pop();

        for (int i = head[t]; i; i = e[i].next) {
            int to = e[i].to;
            if (dep[to] > dep[t] + 1 && e[i].w) {
                dep[to] = dep[t] + 1;
                q.push(to);
            }
        }
    }
    if (dep[T] < INF) return true;
    else return false;
}

int dinic(int u, int limit) {
    if (u == T) return limit; 
    int rest = limit;
    for (int i = head[u]; i && rest; i = e[i].next) {
        int to = e[i].to;
        if (dep[to] == dep[u] + 1 && e[i].w) {
            int k = dinic(to, min(rest, e[i].w));
            if (!k) dep[to] = INF;
            rest -= k;
            e[i].w -= k;
            e[i ^ 1].w += k;
        }
    }
    return limit - rest;
}

int n, m, k;
int h[N], r[N];
vector<int> a[N];

int turn(int x, int c) {
    return c * (n + 2) + x;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        cin >> h[i];
        cin >> r[i];
        a[i].resize(r[i]);
        for (auto& x : a[i]) {
            cin >> x;
            if (x == 0) x = n + 1;
            else if (x == -1) x = n + 2;
        }
    }
    S = 0, T = N - 1;
    add(S, turn(n + 1, 0), k);
    int maxflow = 0;
    for (int c = 1; c <= 7; c++) {
        // cout << "first" << n + 2 << ' ' << c << endl;
        add(turn(n + 2, c), T, INF);
        for (int i = 1; i <= n + 1; i++) add(turn(i, c - 1), turn(i, c), INF);
        for (int i = 1; i <= m; i++) {
            int lst = ((c - 1) % r[i] + r[i]) % r[i];
            int cur = c % r[i];
            // cout << a[i][lst] << ' ' << c - 1 << endl;
            // cout << a[i][cur] << ' ' << c << endl;
            add(turn(a[i][lst], c - 1), turn(a[i][cur], c), h[i]);
        }
        int flow = 0;
        while (bfs()) while (flow = dinic(S, INF)) maxflow += flow;
        if (maxflow == k) {
            cout << c << '\n';
            return 0;
        }
    }
    cout << 0 << '\n';
    return 0;
}