1 条题解

  • 0
    @ 2025-10-8 16:49:23
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 410, M = 1e6 + 10;
    struct edge { int x, y, f, pre; }a[M]; int alen, last[N], cur[N];
    void ins(int x, int y, int f)
    {
        ++alen; a[alen] = edge{ x, y, f, last[x] }; last[x] = alen;
        ++alen; a[alen] = edge{ y, x, 0, last[y] }; last[y] = alen;
    }
    int h[N], st, ed;
    bool bfs()
    {
        deque<int> Q; Q.clear();
        memset(h, 0, sizeof(h)); h[st] = 1;
        Q.push_back(st);
        while (!Q.empty())
        {
            int x = Q.front(); Q.pop_front();
            for (int k = last[x]; k; k = a[k].pre) if (a[k].f)
            {
                int y = a[k].y;
                if (h[y] == 0)
                {
                    h[y] = h[x] + 1;
                    Q.push_back(y);
                }
            }
        }
        return h[ed] > 0;
    }
    int dinic(int x, int f)
    {
        if (x == ed) return f;
        int sx = 0;
        for (int k = cur[x]; k > 0; k = a[k].pre) if (a[k].f)
        {
            cur[x] = k;
            int y = a[k].y;
            if (h[y] == h[x] + 1)
            {
                int sy = dinic(y, min(a[k].f, f - sx));
                a[k].f -= sy; a[k ^ 1].f += sy;
                sx = sx + sy; if (sx == f) return f;
            }
        }
        if (sx == 0) h[x] = 0;
        return sx;
    }
    int main()
    {
        int n, F, D; scanf("%d%d%d", &n, &F, &D);
        alen = 1; memset(last, 0, sizeof(last));
        st = F + D + 2 * n + 1; ed = st + 1;
        for (int i = 1; i <= F; i++) ins(st, i, 1);
        for (int i = 1; i <= D; i++) ins(F + 2 * n + i, ed, 1);
        for (int i = 1; i <= n; i++) ins(F + i, F + n + i, 1);
        for (int i = 1; i <= n; i++)
        {
            int Fi, Di, Fx, Dx; scanf("%d%d", &Fi, &Di);
            for (int j = 1; j <= Fi; j++) scanf("%d", &Fx), ins(Fx, F + i, 1);
            for (int j = 1; j <= Di; j++) scanf("%d", &Dx), ins(F + n + i, F + 2 * n + Dx, 1);
        }
        int s = 0;
        while (bfs())
        {
            memcpy(cur, last, sizeof(last));
            s += dinic(st, 1 << 30);
        }
        printf("%d", s);
        return 0;
    }
    
    • 1

    *【网络流】晚餐[USACO07OPEN] Dining G

    信息

    ID
    308
    时间
    2000ms
    内存
    128MiB
    难度
    7
    标签
    递交数
    271
    已通过
    66
    上传者