题目描述
假设有来自m 个不同单位的代表参加一次国际会议。每个单位的代表数分别为ri (i =1,2,……,m)。
会议餐厅共有n 张餐桌，每张餐桌可容纳ci (i =1,2,……,n)个代表就餐。
为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。
对于给定的代表数和餐桌数以及餐桌容量，编程计算满足要求的代表就餐方案。
输入输出格式
输入格式：
第1 行有2 个正整数m 和n，m 表示单位数，n 表示餐桌数，1<=m<=150, 1<=n<=270。
第2 行有m 个正整数，分别表示每个单位的代表数。
第3 行有n 个正整数，分别表示每个餐桌的容量。
输出格式：
如果问题有解，第1 行输出1，否则输出0。接下来的m 行给出每个单位代表的就餐桌号。如果有多个满足要求的方案，只要输出1 个方案。
输入输出样例
输入样例#1： 复制
4 5
4 5 3 5
3 5 2 6 4
输出样例#1： 复制
1
1 2 4 5
1 2 3 4 5
2 4 5
1 2 3 4 5
圆桌问题
网络流，是一个匹配问题。
可以把求一个人员的分配，转化成一个网络流问题
转化：
这个题目是要求所有的人都可以合理的分配到每一个桌子，这个所谓的合理就是一个单位的不许坐在一起。
所以就建一个图，把每一个单位都和所有的桌子连一条权值为1的线，意思是这个单位只能分配一个人到这里。
然后每一个单位到源点连一根线这根线权值是这个单位的人，然后就是每一个桌子连一根线到汇点，线的权值就是桌子能做的人。
这就是建图，然后你会发现，如果我们要合理分配，那么就是从源点到汇点的最大流为所有单位人之和。
也就是源点连的每一条线的边权值。
建图之后就是一个dinic的板子。
然后就是一个一个路径的输出，这个路径的输出很简单，就是判断这条边（就是单位到桌子）的负边的权值是不是-1，
如果是，则说明这个单位有一个人坐在这里。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <iostream>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + ;
int s, t, n, m;
struct node
{
int from, to, cap, flow;
node(int from=,int to=,int cap=,int flow=):from(from),to(to),cap(cap),flow(flow){}
};
vector<node>e;
vector<int>G[maxn];
int level[maxn], iter[maxn], head[maxn];
void add(int u,int v,int c)
{
e.push_back(node(u, v, c, ));
e.push_back(node(v, u, , ));
int len = e.size();
G[u].push_back(len - );
G[v].push_back(len - );
} void bfs(int s)
{
memset(level, -, sizeof(level));
queue<int>que;
que.push(s);
level[s] = ;
while(!que.empty())
{
int u = que.front(); que.pop();
for(int i=;i<G[u].size();i++)
{
node &now = e[G[u][i]];
if(level[now.to]<&&now.cap>now.flow)
{
level[now.to] = level[u] + ;
que.push(now.to);
}
}
}
} int dfs(int u,int v,int f)
{
if (u == v) return f;
for(int &i=iter[u];i<G[u].size();i++)
{
node &now = e[G[u][i]];
if(now.cap>now.flow&&level[now.to]>level[u])
{
int d = dfs(now.to, v, min(f, now.cap - now.flow));
if(d>)
{
now.flow += d;
e[G[u][i] ^ ].flow -= d;
return d;
}
}
}
return ;
}
int sum = ;
bool dinic()
{
int flow = ;
while()
{
bfs(s);
if (level[t] < ) return flow==sum;
memset(iter, , sizeof(iter));
int f;
while ((f = dfs(s, t, inf)) > ) flow += f;
}
}
vector<int>to[maxn];
int main()
{
cin >> m >> n;
s = , t = m + n + ;
for(int i=;i<=m;i++)
{
int x;
cin >> x;
sum += x;
add(s, i, x);
}
for(int i=;i<=n;i++)
{
int x;
cin >> x;
add(i + m, t, x);
}
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
{
add(i, j + m, );
}
}
int ans = dinic();
printf("%d\n", ans);
if(ans)
for(int i=;i<=m;i++)
{
for(int j=;j<G[i].size();j++)
{
node now = e[G[i][j] ^ ];
if (now.flow == -) printf("%d ", e[G[i][j]].to-m);
}
printf("\n");
}
return ;
}