首页 > 代码库 > COGS729 圆桌聚餐
COGS729 圆桌聚餐
问题描述：
假设有来自m 个不同单位的代表参加一次国际会议。每个单位的代表数分别为
ri(i=1,2,3...m), 。会议餐厅共有n张餐桌，每张餐桌可容纳c i(i=1,2...n) 个代表就餐。
为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。试设计一个算法，
给出满足要求的代表就餐方案。
«编程任务：
对于给定的代表数和餐桌数以及餐桌容量，编程计算满足要求的代表就餐方案。
«数据输入：
由文件roundtable.in提供输入数据。文件第1行有2 个正整数m和n，m表示单位数，n表
示餐桌数，1<=m<=150, 1<=n<=270。文件第2 行有m个正整数，分别表示每个单位的代表
数。文件第3 行有n个正整数，分别表示每个餐桌的容量。
«结果输出:
程序运行结束时，将代表就餐方案输出到文件roundtable.out中。如果问题有解，在文件第
1 行输出1，否则输出0。接下来的m行给出每个单位代表的就餐桌号。如果有多个满足要
求的方案，只要输出1 个方案。
输入文件示例 输出文件示例
roundtable.in
4 54 5 3 53 5 2 6 4roundtable.out
11 2 4 51 2 3 4 52 4 51 2 3 4 5
最大流问题。
源点S向所有的单位连边，容量为单位人数；
每个单位向所有的桌子连边，容量为1 （只能派一个人）;
每个桌子向汇点T连边，容量为桌子可容纳人数;
跑最大流，如果可以满流，说明问题有解。
检查每一条边，记录每个单位派代表去了哪些桌子，最后输出答案。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 #include<vector> 7 using namespace std; 8 const int mxn=3000; 9 int read(){ 10 int x=0,f=1;char ch=getchar(); 11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10-‘0‘+ch;ch=getchar();} 13 return x*f; 14 } 15 struct edge{ 16 int u,v,nxt,f; 17 }e[mxn*10]; 18 int hd[mxn],mct=1; 19 void add_edge(int u,int v,int f){ 20 e[++mct].v=v;e[mct].u=u;e[mct].f=f;e[mct].nxt=hd[u];hd[u]=mct;return; 21 } 22 int n,m; 23 int S,T; 24 int d[mxn]; 25 bool BFS(int s,int t){ 26 queue<int>q; 27 memset(d,0,sizeof d); 28 d[s]=1; 29 q.push(s); 30 while(!q.empty()){ 31 int u=q.front();q.pop(); 32 for(int i=hd[u];i;i=e[i].nxt){ 33 int v=e[i].v; 34 if(!d[v] && e[i].f){ 35 d[v]=d[u]+1; 36 q.push(v); 37 } 38 } 39 } 40 return d[t]; 41 } 42 int DFS(int u,int lim){ 43 if(u==T)return lim; 44 int tmp,f=0; 45 for(int i=hd[u];i;i=e[i].nxt){ 46 int v=e[i].v; 47 if(d[v]==d[u]+1 && e[i].f){ 48 tmp=DFS(v,min(lim,e[i].f)); 49 e[i].f-=tmp; 50 e[i^1].f+=tmp; 51 lim-=tmp; 52 f+=tmp; 53 if(!lim)return f; 54 } 55 } 56 d[u]=0; 57 return f; 58 } 59 inline int Dinic(){ 60 int res=0; 61 while(BFS(S,T))res+=DFS(S,1e9); 62 return res; 63 } 64 int r[mxn],c[mxn]; 65 vector<int>to[mxn]; 66 int main() 67 { 68 freopen("roundtable.in","r",stdin); 69 freopen("roundtable.out","w",stdout); 70 m=read();n=read(); 71 int i,j; 72 int smm=0; 73 for(i=1;i<=m;i++)r[i]=read(),smm+=r[i];//人数 74 for(i=1;i<=n;i++)c[i]=read();//餐桌容量 75 S=0;T=n+m+1; 76 for(i=1;i<=n;i++){//餐桌 77 add_edge(S,i,c[i]); 78 add_edge(i,S,0); 79 } 80 for(i=1;i<=m;i++){ 81 for(j=1;j<=n;j++){ 82 add_edge(j,i+n,1); 83 add_edge(i+n,j,0); 84 } 85 } 86 for(i=1;i<=m;i++){ 87 add_edge(i+n,T,r[i]); 88 add_edge(T,i+n,0); 89 } 90 int ans=Dinic(); 91 if(ans!=smm){printf("0\n");return 0;} 92 for(i=2;i<=mct;i++){ 93 if(e[i].f && e[i].u!=S && e[i].u!=T && e[i].v!=S && e[i].v!=T && e[i].u>e[i].v){ 94 to[e[i].u-n].push_back(e[i].v); 95 } 96 } 97 printf("1\n"); 98 for(i=1;i<=m;i++){ 99 for(j=0;j<to[i].size();j++){100 printf("%d ",to[i][j]);101 }102 printf("\n");103 }104 return 0;105 }
COGS729 圆桌聚餐
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。