Network flow 24 questions (round table questions)

1. Round table questions

Topic link

The main idea of the topic ：

m Representatives of different units attended an international conference . The first i Units sent r_i A representative .
The conference restaurant has n A dining table , The first i Table can accommodate c_i A representative .
Representatives from the same unit do not eat at the same table .

Ideas ：

First, I want to know how to build a map , Because representatives from the same unit do not eat at the same table , So you can connect each unit with each dining table , Capacity of 1.
Then create a source point by yourself , So connect the source point to each unit , The number of people in capacity .
Create another meeting point , Each table is connected to the meeting point , The capacity is the capacity of each table .

So it is similar to building such a picture ：

Then run from the source point to the sink point with the maximum flow , Just set the maximum flow plate ..

Code ：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
int n,m,flow,ss,tt;
struct node {
    
    int to,next,cost;
}E[N << 1];
int head[N],tot;
void init() {
    
    memset(head,-1,sizeof(head));
    tot=0;
}
void add(int from,int to,int co) {
    
    E[tot].to=to,E[tot].cost=co,E[tot].next=head[from],head[from]=tot++;
    E[tot].to=from,E[tot].cost=0,E[tot].next=head[to],head[to]=tot++;
}
int deaph[N];// Depth of layering diagram 
bool bfs(int s,int t) {
    
    memset(deaph,-1,sizeof(deaph));
    queue<int>q;
    deaph[s]=0;
    q.push(s);
    while(!q.empty()) {
    
        int x=q.front();
        q.pop();
        if(x==t) return true;
        for(int i=head[x];~i;i=E[i].next) {
    
            int now=E[i].to;
            if(deaph[now]==-1&&E[i].cost>0) {
    
                q.push(now);
                deaph[now]=deaph[x]+1;
            }
        }
    }
    return false;
}
int dfs(int s, int t,int flow)
{
    
    if(s == t) {
    
        return flow;
    }
    int ans = 0;
    for(int i = head[s]; ~i; i = E[i].next) {
    
        int &to = E[i].to, w = E[i].cost;
        if(deaph[s] + 1 == deaph[to] && w > 0) {
    
            int tmp = min(flow - ans, w);
            int tf = dfs(to, t, tmp);
            E[i].cost -= tf;
            E[i^1].cost += tf;
            ans += tf;
            if(ans == flow) {
    
                return ans;
            }
        }
    }
    return ans;
}

int Dinic(int s, int t)
{
    
    int ret = 0;
    while (bfs(s, t)) {
    
        ret += dfs(s, t, INF);
    }
    return ret;
}
bool check(int x,int y) {
    
    if(x>=1&&x<=m&&y>=1&&y<=n) return true;
    return false;
}
int main() {
    

    ios::sync_with_stdio(false);
    cin >> m >> n;
    init();
    // Unit number 1~m
    // Table No m+1~m+n
    // Source point 0  Confluence n+m+1
    int sum=0;
    for(int i=1;i<=m;i++) {
    
        cin >> flow;
        sum+=flow;
        add(0,i,flow);
    }
    for(int i=1;i<=n;i++) {
    
        cin >> flow;
        add(m+i,m+n+1,flow);
    }
    for(int i=1;i<=m;i++) {
    
        for(int j=1;j<=n;j++) {
    
            add(i,m+j,1);
        }
    }
    int ans=Dinic(0,n+m+1);
    if(ans!=sum) cout << 0 << endl;
    else {
    
        cout << 1 << endl;
        for(int i=1;i<=m;i++) {
    
            int flag=true;
            for(int j=head[i];~j;j=E[j].next) {
    
                if(!E[j].cost) {
    
                    if(flag) cout << E[j].to-m , flag=false;
                    else cout << " " << E[j].to-m;
                } 
            }
            cout << endl;
        }
    }
    return 0;
}