首页 > 代码库 > 【网络流24题----05】圆桌问题
【网络流24题----05】圆桌问题
«问题描述：
假设有来自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向每个单位连出人数大小容量的边，每个桌子作为二分图右侧的一个点，向T连出一条容量为桌子大小的边，每个单位要向每个桌子连一条容量为1的边，跑一遍最大流，然后看最大流是否有座位数那么多，然后满流的边就是答案。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 501 10 #define llg int 11 #define inf (llg)1e16 12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 13 llg n,m,r[maxn],c[maxn],N,tot; 14 15 struct DINIC 16 { 17 vector<llg>a[maxn],ba[maxn],val[maxn]; 18 llg dl[maxn],deep[maxn],bj[maxn]; 19 20 void insert(llg x,llg y,llg z) 21 { 22 a[x].push_back(y),val[x].push_back(z); 23 a[y].push_back(x),val[y].push_back(0); 24 ba[x].push_back(a[y].size()-1); ba[y].push_back(a[x].size()-1); 25 } 26 27 llg dfs(llg x,llg low) 28 { 29 llg va=0,inc=0; 30 if (x==N) return low; 31 llg w=a[x].size(); 32 for (llg i=0;i<w;i++) 33 if (deep[x]+1==deep[a[x][i]] && val[x][i]>0 && (va=dfs(a[x][i],min(low,val[x][i])))) 34 { 35 val[x][i]-=va; val[a[x][i]][ba[x][i]]+=va; inc+=va; 36 return va; 37 } 38 if (!inc) deep[x]=-1; 39 return 0; 40 } 41 42 void fencen() 43 { 44 llg x,w,v; deep[0]=0; 45 memset(bj,0,sizeof(bj)); 46 llg head=0,tail=1; dl[1]=0; bj[0]=1; 47 do 48 { 49 x=dl[++head]; w=a[x].size(); 50 for (llg i=0;i<w;i++) 51 { 52 v=a[x][i]; 53 if (bj[v] || val[x][i]<=0) continue; 54 dl[++tail]=v; 55 deep[v]=deep[x]+1; bj[v]=1; 56 } 57 }while (head!=tail); 58 } 59 60 llg dinic() 61 { 62 llg ans=0; 63 while (1) 64 { 65 fencen(); 66 if (!bj[N]) break; 67 ans+=dfs(0,inf); 68 } 69 return ans; 70 } 71 72 void oupt() 73 { 74 for (llg i=1;i<=m;i++) 75 { 76 llg w=a[i].size(); 77 for (llg k=0;k<w;k++) 78 { 79 llg v=a[i][k]; 80 if (v>m && v<N && val[i][k]==0) cout<<v-m<<" "; 81 } 82 cout<<endl; 83 } 84 } 85 }G; 86 87 void init() 88 { 89 cin>>m>>n; 90 for (llg i=1;i<=m;i++) scanf("%d",&r[i]),tot+=r[i]; 91 for (llg i=1;i<=n;i++) scanf("%d",&c[i]); 92 for (llg i=1;i<=m;i++) 93 { 94 G.insert(0,i,r[i]); 95 for (llg j=1;j<=n;j++) G.insert(i,m+j,1); 96 } 97 for (llg i=1;i<=n;i++) G.insert(m+i,n+m+1,c[i]); 98 N=n+m+1; 99 }100 101 int main()102 {103 yyj("roundtable");104 init();105 if (G.dinic()==tot)106 {107 puts("1");108 G.oupt();109 }110 else111 {112 puts("0");113 }114 return 0;115 }
【网络流24题----05】圆桌问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。