本文正體字版由OpenCC轉換

【問題分析】

二分圖多重匹配問題，可以用最大流解決。

【建模方法】

建立二分圖，每個單位爲X集合中的頂點，每個餐桌爲Y集合中的頂點，增設附加源S和匯T。

1、從S向每個Xi頂點連接一條容量爲該單位人數的有向邊。 2、從每個Yi頂點向T連接一條容量爲該餐桌容量的有向邊。 3、X集合中每個頂點向Y集合中每個頂點連接一條容量爲1的有向邊。

求網絡最大流，如果最大流量等於所有單位人數之和，則存在解，否則無解。對於每個單位，從X集合對應點出發的所有滿流邊指向的Y集合的頂點就是該單位人員的安排情況（一個可行解）。

【建模分析】

對於一個二分圖，每個頂點可以有多個匹配頂點，稱這類問題爲二分圖多重匹配問題。X，Y集合之間的邊容量全部是1，保證兩個點只能匹配一次（一個餐桌上只能有一個單位的一個人），源匯的連邊限制了每個點匹配的個數。求出網絡最大流，如果流量等於X集合所有點與S邊容量之和，那麼則說明X集合每個點都有完備的多重匹配。

【問題另解】

貪心，更好的方法其實是貪心。首先把所有單位和餐桌按人數從大到小排序，一種適當的貪心策略就是對於每個單位，所有人每次儘量去剩餘容量較大的餐桌就坐。按照這種貪心策略，如果某時發現有人已經無法就坐，則無解。具體方法爲用線段樹維護餐桌的剩餘容量，按人數從多到少安排每個單位的人員，每次安排就是把容量餐桌前k大的餐桌人數減1（k爲該單位人數）。爲保證線段樹前k位時刻爲前k大，要維護第k與第k+1,k+2,…人數與第k相等的位置，減少第k大時要減少儘量靠後的，這樣才能保證單調。

圓桌問題
問題描述: 假設有來自 n 個不同單位的代表參加一次國際會議。每個單位的代表數分別爲ri ,i =1,2,...,n。會議餐廳共有 m 張餐桌,每張餐桌可容納ci (i =1,2,...,m)個代表就餐。爲了使代表們充分交流,希望從同一個單位來的代表不在同一個餐桌就餐。試設計一個算法, 給出滿足要求的代表就餐方案。
編程任務: 對於給定的代表數和餐桌數以及餐桌容量,編程計算滿足要求的代表就餐方案。
́數據輸入: 由文件 input.txt 提供輸入數據。文件第 1 行有 2 個正整數 m 和 n,m 表示單位數,n 表示餐桌數,1<=m
結果輸出:
程序運行結束時,將代表就餐方案輸出到文件 output.txt 中。如果問題有解,在文件第 1 行輸出 1,否則輸出 0。接下來的 m 行給出每個單位代表的就餐桌號。如果有多個滿足要求的方案,只要輸出 1 個方案。
輸入文件示例
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

上次修改時間 2017-02-03