欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - PowerOJ1740 - 有SPJ - 推荐
题目传送门 - CodeVS1905 - 无SPJ - 0% 通过率（可以用来看题目）
题意概括
有n支队伍，m个组。第i支队伍有a[i]个人，第i个组最多可以有b[i]个人。
现在要求任何两个同队队员不可位于同一组，求是否有方案满足。
输出第一行，表示是否有，如果有，是1，没有的话，输出0；
如果有，接下来n行，第i行a[i]个数，表示第i支队伍的每个人被安排的组号。
有SPJ，只要输出任意一种方案即可。
题解
其实就是一个网络流的水题。
前置技能 - 网络流（传送门）
对于n支队伍，每只队伍一个点；对于m个组（餐桌），每个组一个点。
另外地，建立一个源点和一个汇点。
连接源点和队伍点，对于队伍i，该边的容量为a[i]；
连接每一个组的点和汇点，对于组i，该边的容量为b[i]；
对于每一个队伍，向每个组连一条边，容量为1。
那么图就构建完了。
至于证明，不解释了。
然后跑一跑最大流，就算出了最大匹配数。
其实，我们可以发现，这是一个二分图多重匹配问题。
如果无法全部匹配，则输出0，
否则输出1，再考虑。
然后对于连接二分图左右两端的边，如果容量为1，那么这条边就是被选择的，那么该边所连接的两个节点，“队伍点”对应“组点”，然后这样就可以把所有的匹配全部还原。
具体操作见代码。
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
const int N=,M=N*N,Inf=<<;
struct Edge{int x,y,cap,flow,nxt,flag;};
struct Graph{
int cnt,s,t,n,fst[N],dist[N],cur[N],num[N],p[N],head,tail,q[N];
Edge e[M];
void set(int S,int T,int nn){
s=S,t=T,n=nn,cnt=,memset(fst,,sizeof fst);
}
void add(int a,int b,int c,int d){
e[++cnt].x=a,e[cnt].y=b,e[cnt].cap=c,e[cnt].flow=,e[cnt].flag=d,e[cnt].nxt=fst[a],fst[a]=cnt;
e[++cnt].x=b,e[cnt].y=a,e[cnt].cap=,e[cnt].flow=,e[cnt].flag=,e[cnt].nxt=fst[b],fst[b]=cnt;
}
void re_bfs(){
memset(dist,-,sizeof dist);
memset(q,,sizeof q);
head=tail=dist[t]=;
q[++tail]=t;
while (head<tail)
for (int x=q[++head],i=fst[x];i;i=e[i].nxt)
if (e[i].cap==&&dist[e[i].y]==-)
dist[q[++tail]=e[i].y]=dist[x]+;
for (int i=;i<=n;i++)
if (dist[i]==-)
dist[i]=n;
}
int Augment(int &point){
int ex_Flow=Inf;
for (int i=t;i!=s;i=e[p[i]].x)
if (ex_Flow>=e[p[i]].cap-e[p[i]].flow)
ex_Flow=e[p[i]].cap-e[p[i]].flow,point=e[p[i]].x;
for (int i=t;i!=s;i=e[p[i]].x)
e[p[i]].flow+=ex_Flow,e[p[i]^].flow-=ex_Flow;
return ex_Flow;
}
int SAP(){
int x=s,y,MaxFlow=;
memset(num,,sizeof num);
for (int i=;i<=n;i++)
num[dist[i]]++,cur[i]=fst[i];
while (dist[s]<=n){
if (x==t){
MaxFlow+=Augment(x);
continue;
}
bool found=;
for (int i=cur[x];i!=&&!found;i=e[i].nxt)
if (dist[e[i].y]+==dist[x]&&e[i].cap>e[i].flow)
cur[x]=p[e[i].y]=i,x=e[i].y,found=;
if (found)
continue;
int d=n+;
for (int i=fst[x];i;i=e[i].nxt)
if (e[i].cap>e[i].flow)
d=min(d,dist[e[i].y]+);
if (!(--num[dist[x]]))
return MaxFlow;
num[dist[x]=d]++,cur[x]=fst[x];
if (x!=s)
x=e[p[x]].x;
}
return MaxFlow;
}
}g;
int n,m,a[N],b[N],sum=,mat[N][N];
int main(){
scanf("%d%d",&n,&m);
g.set(n+m+,n+m+,n+m+);
for (int i=;i<=n;i++)
scanf("%d",&a[i]),sum+=a[i],g.add(g.s,i,a[i],);
for (int i=;i<=m;i++)
scanf("%d",&b[i]),g.add(i+n,g.t,b[i],);
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
g.add(i,j+n,,);
g.re_bfs();
int Flow=g.SAP();
puts(Flow<sum?"":"");
if (Flow<sum)
return ;
memset(mat,,sizeof mat);
for (int i=;i<=g.cnt;i++)
if (g.e[i].flag==&&g.e[i].cap==&&g.e[i].flow==){
int x=g.e[i].x,y=g.e[i].y-n;
mat[x][++mat[x][]]=y;
}
for (int i=;i<=n;i++)
sort(mat[i]+,mat[i]+mat[i][]+);
for (int i=;i<=n;puts(""),i++)
for (int j=;j<=mat[i][];j++)
printf("%d ",mat[i][j]);
return ;
}