ISAP二分图匹配

看到二分图匹配直接上$ISAP$,吊打匈牙利

前置知识:ISAP最大流算法

按照惯例放学长博客 传送门

建图

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

(2) 对于每一对匹配$match_{i,j}$,从$i$到$j$建立容量为$1$的边

代码

正常$ISAP$从超级源点到超级汇点跑最大流,加当前弧优化直接起飞

代码如下(习惯性$O3$)

普通版


#pragma GCC optimize(3)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using std::queue;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

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

Edge *head[MAXN];

int n, m;

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[from]->ops = head[to]; head[to]->ops = head[from];
}

namespace ISAP{
    int s, t, maxflow;
    int dep[MAXN], gap[MAXN];
    
    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 = head[u]; e; e = e->next) {
            int v = e->to;
            if (e->val && dep[v] == dep[u] - 1) {
                int mi = Dfs(v, std::min(e->val, flow - used));
                if (mi) {
                    used += mi;
                    e->val -= mi;
                    e->ops->val += mi;
                    if (used == flow) return used;
                }
            }
        }
        gap[dep[u]]--;
        if (gap[dep[u]] == 0) dep[s] = n + 3;
        dep[u]++;
        gap[dep[u]]++;
        return used;
    }

    void Work() {
        maxflow = 0;
        Bfs();
        while (dep[s] < n + 2) Dfs(s, INF);
    }

    void Print() {
        if (maxflow == 0) {
            puts("No Solution!");
            return;
        }
        printf("%d\n", maxflow);
        for (int i = 1; i <= m; i++) {
            for (Edge *e = head[i]; e; e = e->next) {
                int v = e->to;
                if (v > m && v <= n && e->val == 0) printf("%d %d\n", i, v);
            }
        }
    }
}

int main() {
    scanf("%d %d", &m, &n);
    ISAP::s = 0; ISAP::t = n + 1;
    memset(head, 0, sizeof(head));
    for (int i = 1; i <= m; i++) {
        AddEdge(0, i, 1);
    }
    for (int i = m + 1; i <= n; i++) {
        AddEdge(i, n + 1, 1);
    }
    int x, y;
    while (scanf("%d %d", &x, &y), x != -1 && y != -1) {
        AddEdge(x, y, 1);
    }
    ISAP::Work();
    ISAP::Print();
    return 0;
}
/*
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1
*/

优化版

#pragma GCC optimize(3)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using std::queue;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

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

Edge *head[MAXN];

int n, m;

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[from]->ops = head[to]; head[to]->ops = head[from];
}

namespace ISAP{
    int s, t, maxflow;
    int dep[MAXN], gap[MAXN];
    Edge *cur[MAXN];
    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 (e->val && dep[v] == dep[u] - 1) {
                int mi = Dfs(v, std::min(e->val, flow - used));
                if (mi) {
                    used += mi;
                    e->val -= mi;
                    e->ops->val += mi;
                    if (used == flow) return used;
                }
            }
        }
        gap[dep[u]]--;
        cur[u] = head[u];
        if (gap[dep[u]] == 0) dep[s] = n + 3;
        dep[u]++;
        gap[dep[u]]++;
        return used;
    }

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

    void Print() {
        if (maxflow == 0) {
            puts("No Solution!");
            return;
        }
        printf("%d\n", maxflow);
        for (int i = 1; i <= m; i++) {
            for (Edge *e = head[i]; e; e = e->next) {
                int v = e->to;
                if (v > m && v <= n && e->val == 0) printf("%d %d\n", i, v);
            }
        }
    }
}

int main() {
    scanf("%d %d", &m, &n);
    ISAP::s = 0; ISAP::t = n + 1;
    memset(head, 0, sizeof(head));
    for (int i = 1; i <= m; i++) {
        AddEdge(0, i, 1);
    }
    for (int i = m + 1; i <= n; i++) {
        AddEdge(i, n + 1, 1);
    }
    int x, y;
    while (scanf("%d %d", &x, &y), x != -1 && y != -1) {
        AddEdge(x, y, 1);
    }
    ISAP::Work();
    ISAP::Print();
    return 0;
}
/*
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1
*/