Posted on 2007-04-16 13:27
oyjpart 閱讀(2648)
評論(7) 編輯 收藏 引用 所屬分類:
ACM/ICPC或其他比賽
遇到下面一個題目
給出一個有向圖的各個點(diǎn)的in-degree和out-degree的時候 怎樣求得這個圖的邊的情況？
答案是：
1.把所有的in-degree和所有的out-degree相加，如果不相等 則此圖無法建成 輸出impossible
2.如果可能建 立即得出邊應(yīng)該為 M = sum(in-degree) 因?yàn)槊織l邊必然導(dǎo)致 indegree+1
3.對這個M條邊做分配 如何分配呢？ 如下方案可滿足要求：
最大流算法
1.將每個點(diǎn)化成入點(diǎn)和出點(diǎn)（1分為2）
由于對于有向圖中的邊是從A的出點(diǎn)到B的入點(diǎn) 所以應(yīng)該如下建圖：
2.引出source從所有有向圖中的點(diǎn)的出點(diǎn)的邊 權(quán)為out-degree
3.引出所有有向圖中的點(diǎn)的入點(diǎn)的邊到sink的邊 權(quán)為 in-degree
4.引出所有有向圖任一點(diǎn)到另一點(diǎn)的邊 權(quán)統(tǒng)一為1（在沒有重邊的題目要求下）
5.執(zhí)行最大流算法 如果得到 M 的最大流 則滿足題意 輸出所有這些邊
(如是從B點(diǎn)的出點(diǎn)到A的入點(diǎn) 則輸出B->A)