# Round Table Problem Network Flow 24 Questions (5/24)

Round table problem

Topic: Assume that representatives from m different units attend an international conference. The representation of each unit is ri (i =1,2,...). (m).

There are n tables in the conference dining room. Each table can accommodate ci (i =1,2,...). n) Representatives eat.
In order to make the delegates fully communicate, it is hoped that the delegates from the same unit will not eat at the same table. Try to design an algorithm and give a representative meal plan that meets the requirements.
For a given number of Representatives and dining tables and dining table capacity, the program calculates the representative dining plan that meets the requirements.

Input format
There are two positive integers m and N in the first line. m means the number of units. n means the number of tables. 1<=m<=150,1<=n<=270.
Line 2 has m positive integers, representing the number of representatives of each unit.

Line 3 has n positive integers representing the capacity of each table.

Output format
If the problem is solved, the first line outputs 1, otherwise 0. The next m lines give the table number for each unit. If there are multiple schemes to meet the requirements, only one scheme is output.
Ideas: naked dinic maximum flow template

```#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 10005;
int n, m, ss, tt;
int dis[N];
int cur[N];
queue<int> q;

struct Edge {
int to;
int value;
int next;
} e[N * 10];
int head[N], cnt = -1;
void add(int from, int to, int value) {
cnt++;
e[cnt].to = to;
e[cnt].value = value;
e[cnt].next = head[from];
head[from] = cnt;
}

bool bfs(int s, int t) {
q = queue<int>();
memset(dis, -1, sizeof(dis));
dis[s] = 0;
q.push(s);
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; i > -1; i = e[i].next) {
int now = e[i].to;
if (dis[now] == -1 && e[i].value != 0) {
dis[now] = dis[x] + 1;
q.push(now);
}
}
}
return dis[t] != -1;
}

int dfs(int x, int t, int maxflow) {
if (x == t)
return maxflow;
int ans = 0;
for (int i = cur[x]; i > -1; i = e[i].next) {
int now = e[i].to;
if (dis[now] != dis[x] + 1 || e[i].value == 0 || ans >= maxflow)
continue;
cur[x] = i;
int f = dfs(now, t, min(e[i].value, maxflow - ans));
e[i].value -= f;
e[i ^ 1].value += f;
ans += f;
}
return ans;
}
int Dinic(int s, int t) {
int ans = 0;
while (bfs(s, t)) {
memcpy(cur, head, sizeof(head));
ans += dfs(s, t, INF);
}
return ans;
}
int main() {
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
int a, b,ans=0;
ss = 0, tt = n + m + 1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
add(0,i,a);
add(i,0,0);
ans+=a;
}
for(int i=1;i<=m;i++)
{
scanf("%d",&a);
add(n+i,tt,a);
add(tt,n+i,0);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
add(i,n+j,1);
add(n+j,i,0);
}
}
if(ans!=Dinic(ss, tt))
{
puts("0");
return 0;
}
puts("1");
for(int i=1;i<=n;i++)
{
int t=head[i];
while(t!=-1)
{
if(!e[t].value)
printf("%d ",e[t].to-n);
t=e[t].next;
}
printf("\n");
}
return 0;
}
```

Added by cdorob on Tue, 01 Oct 2019 15:47:47 +0300