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
题解：
(S,每个代表团i,ri) (每一张餐桌i,T,ci) (每一个代表团i,每一个餐桌j,1).
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int N=605,INF=1999999999; 7 int gi(){ 8 int str=0;char ch=getchar(); 9 while(ch>'9'||ch<'0')ch=getchar(); 10 while(ch>='0' && ch<='9')str=str*10+ch-'0',ch=getchar(); 11 return str; 12 } 13 int n,m,S=0,T,num=1,head[N],sum1=0,sum2=0; 14 struct Lin{ 15 int next,to,dis; 16 }a[N*N]; 17 void init(int x,int y,int z){ 18 a[++num].next=head[x]; 19 a[num].to=y; 20 a[num].dis=z; 21 head[x]=num; 22 a[++num].next=head[y]; 23 a[num].to=x; 24 a[num].dis=0; 25 head[y]=num; 26 } 27 int q[N],dep[N]; 28 bool bfs() 29 { 30 memset(dep,0,sizeof(dep)); 31 q[1]=S;dep[S]=1;int t=0,sum=1,x,u; 32 while(t!=sum) 33 { 34 x=q[++t]; 35 for(int i=head[x];i;i=a[i].next){ 36 u=a[i].to; 37 if(dep[u] || a[i].dis<=0)continue; 38 dep[u]=dep[x]+1;q[++sum]=u; 39 } 40 } 41 return dep[T]; 42 } 43 int dfs(int x,int flow) 44 { 45 if(x==T || !flow)return flow; 46 int tmp,sum=0,u; 47 for(int i=head[x];i;i=a[i].next){ 48 u=a[i].to; 49 if(dep[u]!=dep[x]+1 || a[i].dis<=0)continue; 50 tmp=dfs(u,min(flow,a[i].dis)); 51 a[i].dis-=tmp;a[i^1].dis+=tmp; 52 sum+=tmp;flow-=tmp; 53 } 54 return sum; 55 } 56 int main() 57 { 58 int x; 59 n=gi();m=gi(); 60 T=n+m+1; 61 for(int i=1;i<=n;i++){ 62 x=gi();init(S,i,x);sum1+=x; 63 } 64 for(int i=1;i<=m;i++){ 65 x=gi();init(i+n,T,x);sum2+=x; 66 } 67 if(sum1>sum2){ 68 printf("0"); 69 return 0; 70 } 71 for(int i=1;i<=n;i++) 72 for(int j=n+1;j<=n+m;j++)init(i,j,1); 73 int tot=0,tmp; 74 while(bfs()){ 75 tmp=dfs(S,INF); 76 while(tmp)tot+=tmp,tmp=dfs(S,INF); 77 } 78 if(tot<sum1){ 79 printf("0"); 80 return 0; 81 }else printf("1 "); 82 for(int i=1;i<=n;i++){ 83 for(int k=head[i];k;k=a[k].next){ 84 if(a[k].to && a[k].dis==0)printf("%d ",a[k].to-n); 85 } 86 printf(" "); 87 } 88 return 0; 89 }