传送门 ↬\looparrowright

题目描述

有来自 mm 个不同单位的代表参加一次国际会议。第 ii 个单位派出了 rir_i 个代表。
会议的餐厅共有 nn 张餐桌，第 ii 张餐桌可容纳 cic_i 个代表就餐。
为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。请给出一个满足要求的代表就餐方案。

输入格式

输入的第一行是用空格隔开的两个整数，分别代表单位的个数 mm 和餐桌的个数 nn。
第二行有 mm 个用空格隔开的整数，第 ii 个整数代表第 ii 个单位的代表人数 rir_i。
第三行有 nn 个用空格隔开的整数，第 ii 个整数代表第 ii 张餐桌能容纳的人数 cic_i。

输出格式

本题存在 Special Judge。
请输出是否存在满足要求的就餐方案，若存在，请给出任意一种可行的方案。
输出的第一行是一个非 00 即 11 的整数，若存在方案则输出 11，否则输出 00。
若存在方案，则对于第 22 到第 (m+1)(m + 1) 行，在第 (i+1)(i + 1) 行输出 rir_i 个整数，代表第 ii 个单位的代表就餐的餐桌编号。

输入输出样例

输入 #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

说明/提示

数据规模与约定

对于 $100\%$ 的数据，保证 1⩽m⩽1501 \leqslant m \leqslant 150，1⩽n⩽2701 \leqslant n \leqslant 270，1⩽ri,ci⩽1031 \leqslant r_i, c_i \leqslant 10^3。

提示

请注意输入的第一行先读入 mm 再读入 nn。

分析

每个单位和每张餐桌各自都相互独立，只有单位的代表和餐桌会产生联系；要将 mm 个单位的代表分配到 nn 张餐桌上，显然可以转化为二分图多重匹配问题。
二分图左部为表示单位的节点，编号为 1∼m1\sim m；右部为表示餐桌的节点，编号为 m+1∼m+nm+1\sim m+n。进一步，我们要将二分图多重匹配问题转化为网络最大流问题。设立超级源点 ss，超级汇点 tt。ss 向 1∼m1\sim m 的节点连边，容量为各自单位的代表人数 rir_i，现实意义是每个单位至多有 rir_i 个人能分到餐桌；m+1∼m+nm+1\sim m+n 的节点向 tt 连边，容量为各个餐桌的容纳人数 cic_i，现实意义是每个餐桌至多容纳 cic_i 人就餐；1∼m1\sim m 各个点都向 m+1∼m+nm+1\sim m+n 的节点连边，容量为 11，每个单位节点都会向 nn 个餐桌节点连边，总共建立 mnmn 条边，通过限制容量为 11，就限制了每张餐桌不可有相同单位的人同时就餐的条件。由于通过节点之间建边，已经满足题目匹配条件：每个单位有 rir_i 个代表，每张餐桌至多容纳 cic_i 人，同一个单位的不同代表不能分配到同一张餐桌。因此，网络最大流至多等于代表的总人数。
洛谷 P3254.png
运行一次 Dinic\text{Dinic} 算法，即可求得网络最大流 maxflowmaxflow。若最大流小于代表总人数，则不存在合法的匹配方案。若 maxflowmaxflow 等于代表总人数，考虑输出匹配方案。由于单位节点和餐桌节点之间的连边容量至多为 11，因此边上只会存在零流和满流两种状态；若 ii 指向 jj 的边剩余容量为 00（i,j∈N∗i,j\in\mathbb{N^\ast}，且 1⩽i⩽m1\leqslant i\leqslant m，1⩽j−m⩽n1\leqslant j-m\leqslant n），说明该边满流，第 ii 个单位有一人被分配到 j−mj-m 号餐桌。因此，我们不妨枚举左部点的出边，若该边剩余容量为 00，则输出该边的入点。

代码

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P3254
Date: 7/27/2020 
Description: Maximum Flow
*******************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=503;
const int inf=0x3f3f3f3f;
struct E
{
	int to;
	int cap;
	int Next=-1;
}edge[N*N<<1];
int head[N],tot;
int s,t;
int depth[N];
int m,n;//单位个数 餐桌个数
int in;
void init();
inline void add_edge(int,int,int);
bool bfs();
int dfs(int,int);
int Dinic();
int main()
{
	int i,j;
	cin>>m>>n;
	init();
	//与超级源点连边
	for(i=1;i<=m;i++)
	{
		int r;
		scanf("%d",&r);
		add_edge(s,i,r);
		in+=r;//统计人数
	}
	//左右两部之间连边
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			add_edge(i,j+m,1);
		}
	}
	//与超级汇点连边
	for(i=1;i<=n;i++)
	{
		int c;
		scanf("%d",&c);
		add_edge(i+m,t,c);
	}
	if(Dinic()==in)
	{
		puts("1");
		//枚举左部的单位
		for(i=1;i<=m;i++)
		{
			//访问右部节点
			for(j=head[i];~j;j=edge[j].Next)
			{
				if(!edge[j].cap)
				{
					printf("%d ",edge[j].to-m);
				}
			}
			putchar('\n');
		}
	}
	else puts("0");
	return 0;
}
void init()
{
	tot=1;
	memset(head,-1,sizeof(head));
	s=0;
	t=n+m+1;
}
inline void add_edge(int u,int v,int cap)
{
	tot++;
	edge[tot].to=v;
	edge[tot].cap=cap;
	edge[tot].Next=head[u];
	head[u]=tot;
	//建立反边
	tot++;
	edge[tot].to=u;
	edge[tot].cap=0;
	edge[tot].Next=head[v];
	head[v]=tot;
}
bool bfs()
{
	memset(depth,0,sizeof(depth));
	queue<int>q;
	q.push(s);
	depth[s]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(register int i=head[x];~i;i=edge[i].Next)
		{
			int y=edge[i].to;
			//残量网络上构建分层图
			if(edge[i].cap&&!depth[y])
			{
				q.push(y);
				depth[y]=depth[x]+1;
				if(y==t) return 1;//汇点可达
			}
		}
	}
	return 0;
}
int dfs(int x,int flow)//当前节点 当前流量
{
	//dfs 返回残量网络上可增广的流量
	if(x==t) return flow;
	int rest=flow;//rest 剩余流量
	int temp;
	for(register int i=head[x];~i&&rest;i=edge[i].Next)
	{
		int y=edge[i].to;
		if(edge[i].cap&&depth[y]==depth[x]+1)
		{
			temp=dfs(y,min(rest,edge[i].cap));
			if(!temp) depth[y]=0;//剪枝 去掉增广完毕的点
			edge[i].cap-=temp;
			edge[i^1].cap+=temp;
			rest-=temp;
		}
	}
	return flow-rest;
}
int Dinic()
{
	int maxflow=0;
	while(bfs()) maxflow+=dfs(s,inf);
	return maxflow;
}

后记

边的数量 tottot 必须初始化为 11。