网络流24题之 圆桌问题
Description
假设有来自n 个不同单位的代表参加一次国际会议。每个单位的代表数分别为
ri,i=1,2,...,n 。会议餐厅共有m张餐桌，每张餐桌可容纳ci(i=1,2, ,m)个代表就餐。
为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，给出满足要求的代表就餐方案。编程任务：对于给定的代表数和餐桌数以及餐桌容量，编程计算满足要求的代表就餐方案。
Input
由文件input.txt提供输入数据。文件第1行有2 个正整数m和n，m表示单位数，n表
示餐桌数，1<=m<=150, 1<=n<=270。文件第2 行有m个正整数，分别表示每个单位的代表
数。文件第3 行有n个正整数，分别表示每个餐桌的容量。
Output
程序运行结束时，将代表就餐方案输出到文件output.txt 中。如果问题有解，在文件第
1 行输出1，否则输出0。接下来的m行给出每个单位代表的就餐桌号。如果有多个满足要
求的方案，只要输出1 个方案。
Sample Input
4 5
4 5 3 5
3 5 2 6 4
Sample Output
1
1 2 4 5
1 2 3 4 5
2 4 5
1 2 3 4 5
思路
二分图多重匹配，把源点向每个单位连边，流量为人数，每个桌子向汇点连边，流量是桌子的人数，每个单位向每个桌子连流量是1的边，如果最大流等于人数，就是1，否则0，然后输出路径即可
#include <bits/stdc++.h>
using namespace std;
const int N = 305;
int a[N], b[N];
struct Dinic {
static const int MAXN = 500 + 7;
static const int MAXM = MAXN * MAXN;
static const int INF = 0x3f3f3f3f;
int n, m, s, t;
int first[MAXN], cur[MAXN], dist[MAXN], sign;
struct Node {
int to, flow, next;
} edge[MAXM * 4];
inline void init(int start, int vertex, int ss, int tt) {
n = vertex, s = ss, t = tt;
for(int i = start; i <= n; i++ ) {
first[i] = -1;
}
sign = 0;
}
inline void addEdge(int u, int v, int flow) {
edge[sign].to = v, edge[sign].flow = flow, edge[sign].next = first[u];
first[u] = sign++;
}
inline void add_edge(int u, int v, int flow) {
addEdge(u, v, flow);
addEdge(v, u, 0);
}
inline int dinic() {
int max_flow = 0;
while(bfs(s, t)) {
for(int i = 0; i <= n; i++ ) {
cur[i] = first[i];
}
max_flow += dfs(s, INF);
}
return max_flow;
}
bool bfs(int s, int t) {
memset(dist, -1, sizeof(dist));
queue<int>que;
que.push(s), dist[s] = 0;
while(!que.empty()) {
int now = que.front();
que.pop();
if(now == t) {
return 1;
}
for(int i = first[now]; ~i; i = edge[i].next) {
int to = edge[i].to, flow = edge[i].flow;
if(dist[to] == -1 && flow > 0) {
dist[to] = dist[now] + 1;
que.push(to);
}
}
}
return 0;
}
int dfs(int now, int max_flow) {
if(now == t) {
return max_flow;
}
int ans = 0, next_flow = 0;
for(int &i = cur[now]; ~i; i = edge[i].next) {
int to = edge[i].to, flow = edge[i].flow;
if(dist[to] == dist[now] + 1 && flow > 0) {
next_flow = dfs(to, min(max_flow - ans, flow));
ans += next_flow;
edge[i].flow -= next_flow;
edge[i ^ 1].flow += next_flow;
if(ans == max_flow) {
return max_flow;
}
}
}
if(ans == 0) {
return dist[now] = 0;
}
return ans;
}
void show(int n, int m) {
puts("1");
vector<pair<int, int> >vec;
for(int i = n + 1; i <= n + m; i++ ) {
for(int j = first[i]; ~j; j = edge[j].next) {
if(edge[j].flow == 1 && edge[j].to != t) {
//printf("%d %d
", edge[j].to, i);
vec.push_back(make_pair(edge[j].to, i - n));
}
}
}
vector<int>E[MAXN];
for(int i = 0; i < vec.size(); i++ ) {
E[vec[i].first].push_back(vec[i].second);
}
for(int i = 1; i <= n; i++ ) {
for(int j = 0; j < E[i].size(); j++ ) {
if(j) {
printf(" ");
}
printf("%d", E[i][j]);
}
puts("");
}
}
} cwl;
int main() {
int n, m, sum = 0;
scanf("%d %d", &n, &m);
cwl.init(0, n + m + 1, 0, n + m + 1);
for(int i = 1; i <= n; i++ ) {
scanf("%d", &a[i]);
sum += a[i];
}
for(int i = 1; i <= m; i++ ) {
scanf("%d", &b[i]);
}
for(int i = 1; i <= n; i++ ) {
cwl.add_edge(0, i, a[i]);
}
for(int i = n + 1; i <= n + m; i++ ) {
cwl.add_edge(i, n + m + 1, b[i - n]);
}
for(int i = 1; i <= n; i++ ) {
for(int j = 1; j <= m; j++ ) {
cwl.add_edge(i, j + n, 1);
}
}
int ans = cwl.dinic();
if(ans == sum) {
cwl.show(n, m);
} else {
puts("0");
}
return 0;
}