[网络流24题] 圆桌问题（最大流）

题目链接

建边: 因为每一个单位只能有一个人坐在一张桌子上， 所以对于每一个单位与每一张桌子连一条权值为 1 的边， 然后连源点到每一个单位 和 每张桌子到汇点的边，跑最大流，最大流等于所有单位的总人数，就有解，
有解的话，单位与桌子的反向弧为满流就是为方案

#include <bits/stdc++.h>
const int maxn = 250;
const int inf = 0x3f3f3f3f;
using namespace std;
typedef long long ll;

struct note
{
    int u, v, w;
    int next;
} e[maxn * maxn * 2];
int head[maxn * 2], cnt;
int m, n, s, t;
vector<int> ans[maxn];

void add(int u, int v, int w)
{
    e[cnt].u = u, e[cnt].v = v, e[cnt].w = w;
    e[cnt].next = head[u], head[u] = cnt++;

    e[cnt].u = v, e[cnt].v = u, e[cnt].w = 0;
    e[cnt].next = head[v], head[v] = cnt++;
}

int level[maxn * 2];

bool bfs()
{
    queue<int> q;
    memset(level, -1, sizeof(level));
    level[s] = 1;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = e[i].next)
        {
            int v = e[i].v;
            if (e[i].w > 0 && level[v] == -1)
            {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[t] != -1;
}

int dfs(int u, int delta)
{
    if (u == t)
        return delta;
    int flow = 0;
    for (int i = head[u]; ~i; i = e[i].next)
    {
        int v = e[i].v;
        if (e[i].w > 0 && level[v] == level[u] + 1)
        {
            int tmp = dfs(v, min(delta - flow, e[i].w));
            e[i].w -= tmp;
            e[i ^ 1].w += tmp;
            flow += tmp;
        }
    }
    if (!flow)
        level[u] = inf;
    return flow;
}

int Dinic()
{
    int maxflow = 0, tmp;
    while (bfs())
    {
        while ((tmp = dfs(s, inf)))
            maxflow += tmp;
    }
    return maxflow;
}

int main()
{
    scanf("%d%d", &m, &n);
    memset(head, -1, sizeof(head));
    s = 0, t = n + m + 1;
    int he = 0; //总人数
    for (int i = 1; i <= m; i++)
    {
        int tmp;
        scanf("%d", &tmp);
        he += tmp;
        add(s, i, tmp); //连边  源点与人
    }
    for (int i = m + 1; i <= n + m; i++)
    {
        int tmp;
        scanf("%d", &tmp);
        add(i, t, tmp); //连边  桌子余汇点
        for (int j = 1; j <= m; j++)
            add(j, i, 1); //连边  人与桌子
    }
    for (int i = s; i<=t; i++){
        for (int j = head[i]; ~j; j=e[j].next){
            if(e[j].w)
                printf("%d %d %d
", e[j].u, e[j].v, e[j].w);
        }
    }
        int res = Dinic();
    if (he != res) //有人没入座
    {
        printf("0
");
        return 0;
    }
    printf("1
");
    for (int i = 0; i < cnt; i += 2)
    {
        if (e[i].u == s || e[i].v == t)
            continue;
        if (e[i ^ 1].w) //方案
        {
            ans[e[i].u].push_back(e[i].v - m);
        }
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0, len = ans[i].size(); j < len; j++)
        {
            if (j)
                printf(" ");
            printf("%d", ans[i][j]);
        }
        printf("
");
    }
    return 0;
}

这题比较简单，因为建图连边，很明显