题目描述

假设有来自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

分析

建超级源点和超级汇点，源点向每个代表连一条 r i r_i ri​ 的边，每个桌子向汇点连一条 c i c_i ci​ 的边，中间是个完全图，如图。

跑最大流即可。
一个流表示一个代表坐到了一张桌子上。
输出方案的话，看哪些边是 0 0 0 边就好了，说明这条边被流过。
用的是萌萌的 i s a p isap isap 算法求最大流。

代码如下

#include <bits/stdc++.h>
#define N 100005
#define inf 2147483647
using namespace std;
struct node{
	int a, b, c, n;
}d[N * 2];
int dep[N], gap[N], h[N], sum, cnt = 1, ans, cur[N], s, t, n, m, tot, A[N], B[N];

void cr(int a, int b, int c){
	d[++cnt].a = a; d[cnt].b = b; d[cnt].c = c; d[cnt].n = h[a]; h[a] = cnt;
}
void bfs(int a){
	int i, b;

	queue<int> q;
	dep[a] = 1;
	gap[1] = 1;
	q.push(a);
	while(!q.empty()){
		a = q.front();
		q.pop();
		for(i = h[a]; i; i = d[i].n){
			b = d[i].b;

			if(!dep[b]){

				dep[b] = dep[a] + 1;
				gap[dep[b]]++;

				q.push(b);

			}
		}
	}
}
int sap(int a, int flow){
	int i, b, c, w, used = 0;
	if(a == t) return flow;
	for(i = cur[a]; i; i = d[i].n){
		cur[a] = i;
		b = d[i].b;

		c = d[i].c;
		if(dep[a] == dep[b] + 1 && c > 0){
			if(w = sap(b, min(flow - used, c))){
				used += w;
				d[i].c -= w;
				d[i ^ 1].c += w;
			}
			if(used == flow) return used;
		}
	}
	gap[dep[a]]--;
	if(!gap[dep[a]]) dep[s] = tot + 5;
	dep[a]++;
	gap[dep[a]]++;
	return used;
}
int main(){
	int i, j, b, c;
	scanf("%d%d", &n, &m);
	s = n + m + 1;
	t = n + m + 2;
	tot = n + m + 2;
	for(i = 1; i <= n; i++) scanf("%d", &A[i]), sum += A[i];
	for(i = 1; i <= m; i++) scanf("%d", &B[i]);
	for(i = 1; i <= n; i++){
		for(j = 1; j <= m; j++){
			cr(i, j + n, 1);
			cr(j + n, i, 0);
		}
	}
	for(i = 1; i <= n; i++) cr(s, i, A[i]), cr(i, s, 0);
	for(i = 1; i <= m; i++) cr(i + n, t, B[i]), cr(t, i + n, 0);
	bfs(t);

	while(dep[s] < tot + 1){
		for(i = 0; i <= tot; i++) cur[i] = h[i];
		ans += sap(s, inf);
	}
	if(ans != sum) printf("0");
	else{
		printf("1\n");
		for(i = 1; i <= n; i++){
			for(j = h[i]; j; j = d[j].n){
				b = d[j].b;

				c = d[j].c;

				if(!c){
					printf("%d ", b - n);
				}
			}
			printf("\n");
		}
	}
	return 0;
}