二分图匹配,我用的指针版ISAP

二分图匹配ISAP效率极高,尤其是加了当前弧优化

建图

  • 从超级源点向每一个单位连接容量为人数的边
  • 从每一个圆桌向超级汇点连接容量为人数的边
  • 从每一个单位向每一个圆桌连接容量为$1$的边

输出

  • 如果总流量小于总人数,则无解
  • 遍历每一个单位,对于起点为单位终点为圆桌剩余容量为$0$的边,输出终点即圆桌编号

代码

有$cur$优化的$ISAP$

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

using std::queue;

const int MAXM = 155;
const int MAXN = 275;
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) {ops = NULL;}
};

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

int n, m, tot = 0;

namespace ISAP{
    int s, t, maxflow;
    int gap[MAXN + MAXM], dep[MAXN + MAXM];
    Edge *cur[MAXM + 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 + m + 2;
        dep[u]++;
        gap[dep[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 + m + 1) Dfs(s, INF);
    }

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

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