圆桌问题

传送门

题目大意

有一些单位和一些桌子，每个单位都排除了一定量的领导参加会议，从同一个单位来的代表不在同一个桌子上，给出一个满足要求的代表就餐方案。

题目分析

这个题说实话，和飞行员那个题很像，但是有区别的。

还是，考虑dinic如何建图。

先按照二分图思路分两个集合，分别为代表和桌子。这个题和飞行员的区别在于：我可以随便建边，不受限制。比如说我们有俩单位仨桌子。那我们就可以都给他连上就有六个边。即有些边可以共用某些点的。

诶，这就和普通二分图不太一样了哈。（二分图多重匹配问题）

开始考虑网络流建图。

由于从同一个单位来的代表不在同一个桌子上，所以每次只能派给一个桌子一个代表。那我们每条边的容量就是1呗。而源点向集合连边的时候，就要考虑单位的代表数量，作为边的容量。同理，汇点考虑桌子。

显然，该图满足容量限制和流量守恒。

最后，处理比较麻烦的仍然是方案输出。这里的话直接用邻接表可以实现，详见代码。

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 430;
const int M = (150 * 270 + N) * 2;
const int INF = 1e8;

int m, n, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];

void add(int a, int b, int c)
{
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S;
    d[S] = 0;
    cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if (ver == T)
                    return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if (u == T)
        return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if (d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(f[i], limit - flow));
            if (!t)
                d[ver] = -1;
            f[i] -= t;
            f[i ^ 1] += t;
            flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int r = 0, flow;
    while (bfs())
        while (flow = find(S, INF))
            r += flow;
    return r;
}

int main()
{
    cin >> m >> n;
    S = 0;
    T = m + n + 1;
    memset(h, -1, sizeof h);
    int tot = 0;
    for (int i = 1; i <= m; i++)
    {
        int c;
        cin >> c;
        add(S, i, c);
        tot += c;
    }
    for (int i = 1; i <= n; i++)
    {
        int c;
        cin >> c;
        add(m + i, T, c);
    }
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            add(i, m + j, 1);

    if (dinic() != tot)
        puts("0");
    else
    {
        puts("1");
        for (int i = 1; i <= m; i++)
        {
            for (int j = h[i]; ~j; j = ne[j])
            {
                if (e[j] > m && e[j] <= m + n && !f[j])
                {
                    cout << e[j] - m << " ";
                }
            }
            puts("");
        }
    }

    return 0;
}