原题链接

题目大意

有$m$个单位，每个单位有$r_i(i=1,2,…,m)$个人。总$n$张桌子，每张桌子可坐$c_i(i=1,2,…,n)$个人。
问是否存在一种坐法使相同单位的人不在同一张桌子，若存在则输出1，再输出每个单位坐哪几张桌子；若不存在则直接输出0，

解题思路

图是用来表示对象与对象之间的关系的结构。那么建图前首先要分析清题目中的对象，以及对象与对象之间的关系，并将这种关系用图表示出来。

此题中的对象有单位、人、桌子，但实际上人可被化为单位的属性，所以只有单位、桌子两个对象，限制条件有单位的人数、桌子的容量以及相同单位的人不能在同一张桌子。

将单位都当作点，标号为$1\sim m$,桌子标号为$m+1\sim m+n$，为使相同单位的人不在同一张桌子，一个单位与一张桌子之间可仅连接一条容量为1的边，代表一个单位最多有一个人坐到一张桌子上；而一个单位与不同桌子间并没有限制，所以将一个单位与每一张桌子都连边，其他单位同理。还有两个限制条件是每个单位的人数，与桌子的容量，可以通过建立源点与汇点，将源点与第$i$个单位间连接一条容量为$r_i$的边，将第$j$张桌子与汇点间连接一条容量为$c_j$的边来实现限制的效果。

图建完后跑最大流，若得到的结果$maxflow$等于总人数$sum$则说明存在满足题目要求的方案，找出$1\sim m$的顶点中与哪些顶点间的剩余容量为0输出顶点编号即可;
若$maxflow$小于$sum$则说明不存在满足要求的方案，直接输出0;
若$maxflow$大于$sum$则说明图建的有问题.

AC代码

样例输入

4 5
4 5 3 5
3 5 2 6 4

样例输出

1
1 2 4 5
1 2 3 4 5
2 4 5
1 2 3 4 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF = (unsigned int)(-1)>>1;
const int MAX_V=500;
struct edge {
	int to,cap,rev;
};

vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];
void add_edge(int from,int to,int cap) {
	G[from].push_back((edge) {
		to,cap,G[to].size()
	});
	G[to].push_back((edge) {
		from,0,G[from].size()-1
	});
}
void bfs(int s) {
	memset(level,-1,sizeof(level));

	queue<int> que;

	level[s]=0;

	que.push(s);

	while(!que.empty()) {
		int v = que.front();
		que.pop();

		for(int i=0; i<G[v].size(); i++) {
			edge &e = G[v][i];

			if(e.cap > 0 && level[e.to]<0) {
				level[e.to] = level[v] +1;
				que.push(e.to);
			}
		}
	}
}

int dfs(int v,int t,int f) {
	if(v == t)return f;

	for(int &i=iter[v]; i<G[v].size(); i++) {
		edge &e = G[v][i];
		if(e.cap > 0 && level[v] < level[e.to]) {
			int d =dfs(e.to,t,min(f,e.cap));

			if(d>0) {
				e.cap -= d;

				G[e.to][e.rev].cap += d;

				return d;
			}
		}
	}

	return 0;
}

int max_flow(int s, int t) {
	int flow = 0;

	for(;;) {
		bfs(s);

		if(level[t]<0)return flow;
		memset(iter,0,sizeof(iter));

		int f;

		while((f= dfs(s,t,INF))>0) {
			flow += f;
		}
	}
}

int main(){
    int m,n,sum=0;        //1～m团体 m+1~n+m 桌子
    cin>>m>>n;
    int s=0,t=n+m+1;
    int c;
    for(int i=1;i<=m;++i){
        cin>>c;
        sum+=c;
        add_edge(s,i,c);
        for(int j=m+1;j<=n+m;++j){
            add_edge(i,j,1);
        }
    }
    for(int i=m+1;i<=n+m;++i){
        cin>>c;
        add_edge(i,t,c);
    }

    int ans=max_flow(s,t);

    if(ans!=sum){
        cout<<0;
    }
    else{
        cout<<1<<endl;
        for(int i=1;i<=m;++i){
            for(int j=0;j<G[i].size();++j){
                edge &e = G[i][j];

                if(e.cap==0)cout<<e.to-m<<" ";
            }
            cout<<endl;
        }
    }
}