算法實(shí)現(xiàn)題8-5 圓桌問(wèn)題（習(xí)題 8-15）
′問(wèn)題描述：
假設(shè)有來(lái)自 n 個(gè)不同單位的代表參加一次國(guó)際會(huì)議。每個(gè)單位的代表數(shù)分別為
n i ri
, , 2 , 1 , ? = 。會(huì)議餐廳共有 m張餐桌，每張餐桌可容納 ) , , 2 , 1 ( m i ci
? = 個(gè)代表就餐。
為了使代表們充分交流， 希望從同一個(gè)單位來(lái)的代表不在同一個(gè)餐桌就餐。 試設(shè)計(jì)一個(gè)算法，
給出滿足要求的代表就餐方案。
′編程任務(wù)：
對(duì)于給定的代表數(shù)和餐桌數(shù)以及餐桌容量，編程計(jì)算滿足要求的代表就餐方案。
′數(shù)據(jù)輸入：
由文件input.txt提供輸入數(shù)據(jù)。文件第1行有 2 個(gè)正整數(shù)m和 n，m表示單位數(shù)，n表
示餐桌數(shù)，1<=m<=150, 1<=n<=270。文件第 2 行有m個(gè)正整數(shù)，分別表示每個(gè)單位的代表
數(shù)。文件第3行有n個(gè)正整數(shù)，分別表示每個(gè)餐桌的容量。
′結(jié)果輸出:
程序運(yùn)行結(jié)束時(shí)，將代表就餐方案輸出到文件 output.txt 中。如果問(wèn)題有解，在文件第
1行輸出1，否則輸出0。接下來(lái)的m行給出每個(gè)單位代表的就餐桌號(hào)。如果有多個(gè)滿足要
求的方案，只要輸出1個(gè)方案。
輸入文件示例? 輸出文件示例?
輸入文件示例
input.txt
4 5
4 5 3 5
3 5 2 6 4?

輸出文件示例
output.txt
1
1 2 4 5
1 2 3 4 5
2 4 5
1 2 3 4 5?

?

————————————————————

1 Program Stone; 2 var flow,n,m,s,t,tot:longint; 3 map:array[0..500,0..500]of longint; 4 dis,cur,vh:array[0..1000]of longint; 5 procedure init; 6 var i,j,k:longint; 7 begin 8 readln(m,n); 9 s:=0;t:=m+n+1; 10 for i:=1 to m do 11 begin 12 read(j); 13 map[s,i]:=j; 14 inc(tot,j); 15 end; 16 for i:=1 to n do 17 begin 18 read(j); 19 map[i+m,t]:=j; 20 end; 21 for i:=1 to m do 22 for j:=1 to n do 23 map[i,j+m]:=1; 24 end; 25 function min(x,y:longint):longint; 26 begin 27 if x<y then min:=x else min:=y; 28 end; 29 function aug(x,nf:longint):longint; 30 var i,j,d,l,minh,ins:longint; 31 begin 32 if x=t then exit(nf); 33 l:=nf; 34 for i:=cur[x] to t do 35 if (map[x,i]>0)and(dis[i]+1=dis[x]) then 36 begin 37 cur[x]:=i; 38 d:=aug(i,min(l,map[x,i])); 39 dec(map[x,i],d); 40 inc(map[i,x],d); 41 dec(l,d); 42 if (dis[s]=t+1)or(l=0) then exit(nf-l); 43 end; 44 if l=nf then 45 begin 46 minh:=t+1; 47 for i:=s to t do 48 if (map[x,i]>0)and(minh>dis[i]) then begin minh:=dis[i];ins:=i;end; 49 cur[x]:=ins; 50 dec(vh[dis[x]]); 51 if vh[dis[x]]=0 then dis[s]:=t+1; 52 dis[x]:=minh+1; 53 inc(vh[dis[x]]); 54 end; 55 aug:=nf-l; 56 end; 57 procedure print; 58 var i,j:longint; 59 begin 60 if flow<>tot then write(0) 61 else begin 62 writeln(1); 63 for i:=1 to m do 64 begin 65 for j:=1 to n do 66 if map[i,j+m]=0 then write(j,' '); 67 writeln; 68 end; 69 end; 70 end; 71 Begin 72 assign(input,'prog85.in');assign(output,'prog85.out'); 73 reset(input);rewrite(output); 74 init; 75 vh[0]:=t+2; 76 while dis[s]<t+1 do inc(flow,aug(s,maxint)); 77 print; 78 close(input);close(output); 79 end.

?

轉(zhuǎn)載于:https://www.cnblogs.com/yesphet/p/5236402.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的圆桌问题 2011-12-29的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。