一个带当前弧优化的$ISAP$题解

题目大意

有$n$个牛,$m$个牛棚,每头牛有多个可选择的牛棚,求出让尽可能多的牛住进牛棚

前置知识:ISAP算法

可以看pica学长的博客

思路

二分图匹配,可以用最大流,我选择用$ISAP$跑最大流,速度快

建图

(1) 把$0$当做超级源点,向从$1$到$n$所有点建立容量为$1$的边,把$n + m + 1$当做超级汇点,从$n + 1$到$n + m$向它建立容量为$1$的边

(2) 对于牛$i$的所有选择$x_1$到$x_s$,从$i$到$n + x_j$建立容量为$1$的边

输出

跑$ISAP$,直接输出最大流

代码(有当前弧优化)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using std::queue;

const int MAXN = 205;
const int MAXM = 205;
const int INF = 0x3f3f3f3f;

int n, m;

struct Edge{
    int to, val;
    Edge *next, *opps;
    Edge(int to, int val, Edge* next):to(to), val(val), next(next){}
};

Edge *head[MAXN + MAXM];

void AddEdge(int from, int to, int val) {
    head[from] = new Edge(to, val, head[from]);
    head[to] = new Edge(from, 0, head[to]);
    head[to]->opps = head[from]; head[from]->opps = head[to];
}

namespace ISAP{
    Edge *cur[MAXN + MAXM];
    int dep[MAXN + MAXM], gap[MAXN + MAXM];
    int s, t, maxflow = 0;

    void Bfs() {
        memset(dep, -1, sizeof(dep));
        memset(gap, 0, sizeof(gap));
        dep[t] = 0; gap[dep[t]]++;
        queue<int> q;
        q.push(t);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (Edge *e = head[u]; e; e = e->next) {
                int v = e->to;
                if (dep[v] != -1) continue;
                dep[v] = dep[u] + 1;
                gap[dep[v]]++;
                q.push(v);
            }
        }
    }

    int Dfs(int u, int flow) {
        if (u == t) {
            maxflow += flow;
            return flow;
        }
        int used = 0;
        for (Edge *&e = cur[u]; e; e = e->next) {//当前弧优化,需要取址修改当前弧
            int v = e->to;
            if (dep[v] == dep[u] - 1 && e->val) {
                int mi = Dfs(v, std::min(flow - used, e->val));
                if (mi) {
                    used += mi;
                    e->val -= mi;
                    e->opps->val += mi;
                    if (used == flow) return flow;
                }
            }
        }
        gap[dep[u]]--;
        if (gap[dep[u]] == 0) dep[s] = n + 1;
        dep[u]++;
        gap[dep[u]]++;
        cur[u] = head[u];//复原当前弧
        return used;
    }

    void Work() {
        for (int i = 0; i <= n + m + 1; i++) cur[i] = head[i];
        maxflow = 0;
        Bfs();
        while (dep[s] < n) Dfs(s, INF);
    }
}

int main() {
    memset(head, 0, sizeof(head));
    scanf("%d %d", &n, &m);
    ISAP::s = 0; ISAP::t = n + m + 1;
    for (int i = 1; i <= n; i++) AddEdge(0, i, 1);
    for (int i = 1; i <= m; i++) AddEdge(n + i, n + m + 1, 1);
    for (int i = 1, p; i <= n; i++) {
        scanf("%d", &p);
        for (int j = 1, x; j <= p; j++) {
            scanf("%d", &x);
            AddEdge(i, n + x, 1);
        }
    }
    ISAP::Work();
    printf("%d\n", ISAP::maxflow);
    return 0;
}
/*
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2
*/

由于我是个懒人,不愿意算最多有多少条边,所以使用了极其拖慢时间的$new$函数动态开空间建边。但是即使这样,也只跑了$26ms$,说明$ISAP$的效率很高