[网络流24题]P2754 [CTSC1999]家园 / 星际转移

#include 
#define endl '\n'
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0)
#define P pair
typedef long long ll;
using namespace std;

const int N = 2 * 20 * 50 * 2 + 5;
const int M = N * N;
const int INF = 0x3f3f3f3f;

struct edge {
    int v, w, to;
} e[M * 2];
int pre[N], cnt_edge, dep[N];
int S, T, z, head[N], sum;
int n, m, q[N], cur[N];
void add(int u, int v, int w) {
    // cout << "add: " << u << " " << v << endl;
    e[cnt_edge] = {v, w, head[u]};
    head[u] = cnt_edge++;
    e[cnt_edge] = {u, 0, head[v]};
    head[v] = cnt_edge++;
}
bool bfs() {
    for (int i = 0; i <= T; i++) dep[i] = 0;
    dep[S] = 1;
    int l = 0, r = 1;
    q[r] = S;
    while (l < r) {
        int u = q[++l];
        for (int i = head[u]; i != -1; i = e[i].to) {
            int v = e[i].v;
            if (!dep[v] && e[i].w) dep[v] = dep[u] + 1, q[++r] = v;
        }
    }
    return dep[T];
}
int dfs(int u, int mi) {
    int res = 0;
    if (mi == 0 || u == T) return mi;
    for (int &i = cur[u]; i != -1; i = e[i].to) {
        int v = e[i].v;
        if (dep[u] + 1 == dep[v] && e[i].w) {
            int minn = dfs(v, min(mi - res, e[i].w));
            e[i].w -= minn;
            e[i ^ 1].w += minn;
            res += minn;
            if (res == mi) return res;
        }
    }
    if (res == 0) dep[u] = 0;
    return res;
}
int dinic() {
    ll res = 0;
    while (bfs()) {
        memcpy(cur, head, sizeof(head));
        //    cout< s[25];
int id(int day, int x) {
    if ((day - 1) * n + x >= S) flag = 1;
    return min((day - 1) * n + x, T);
}
int main() {
    memset(head, -1, sizeof head);
    S = 4000 + 1, T = S + 1;
    cin >> n >> m >> num;
    for (int i = 1, tmp, o; i <= m; i++) {
        cin >> cap[i] >> tmp;
        for (int j = 0; j < tmp; j++) {
            cin >> o;
            s[i].push_back(o);
        }
    }
    int ans = 0, now = 0;
    while (now < num) {
        if (flag) {
            cout << 0 << endl;
            return 0;
        }
        ans++;
        // cout << ans << " " << now << " \n";
        for (int i = 1; i <= m; i++) {
            int sz = s[i].size();
            int v = s[i][ans % sz], u = s[i][(ans - 1 + sz) % sz];
            // cout << "a: " << u << " " << v << endl;
            if(u == 0 && v == -1){
                now += cap[i];
                continue;
            }
            if (u == 0) {
                add(S, id(ans + 1, v), cap[i]);
                continue;
            }
            if (u == -1) continue;
            if (v == 0) continue;
            if (v == -1) {
                add(id(ans, u), T, cap[i]);
                continue;
            }
            if (ans == 1 && u != S) continue;
            add(id(ans, u), id(ans + 1, v), cap[i]);
        }
        for (int i = 1; i <= n; i++) {
            add(id(ans, i), id(ans + 1, i), INF);
        }
        // puts("----------");
        now += dinic();
    }
    if (flag) {
        cout << 0 << endl;
        return 0;
    }
    cout << ans << endl;
    return 0;
}