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