算法匹配一個圖形

Question

如果我們具有與邊連接（如使用街道的交叉）的節點的數量，並且每個節點具有0至3的邊緣的值具有值0。

現在我想寫一個算法，該算法將節點的值分配給值邊緣，因此在算法終止後，所有節點的值都爲0，並且所有邊的值爲< = 1.

例如，給定此圖：

我想製作此圖：

。

我的解決方案：

我所定義的數據類型隧道和街道：

public class Crossing{ 
    int value; 
} 

public class Street{ 
    int value; 
    Crossing A, B; 
} 

通過交叉算法遍歷和分配的值，以街道（請注意，交叉只能分配其價值到相鄰的街道）。

void allocate(Crossing[] crossings, Street[] streets){ 
    foreach(crossings as c){ //iterate through every Crossing 
     foreach(streets as s){ //Find the streets, which are adjacent to c 
      if((s.A == c || s.B == c) && s.value < 1 && c.value != 0) 
       // The value of the crossing is >0 and the value of the 
       // street is 0. 
       c.value -= 1; 
       s.value += 1; 
     } 
    } 
} 

我的算法能工作嗎？如果是：是否有效，還是有更好的解決方案？

Answer 1

恐怕你的算法不會總是工作。例如，如果我們有節點ABC，其中A和B的值爲1（且C的值爲0），那麼如果將來自B的值賦給AB交叉而不是BC交叉（因爲那麼A值無處可去）。

我會推薦閱讀最大流量算法，例如與this topcoder tutorial

要解決這個問題與最大流量算法，你希望定義一個新的有向圖。這個新圖形爲每個交叉點都有一個節點，並且每個街道都有一個節點（加上一個源節點和匯點節點）。

需要邊緣：

1. 從源到每個具有容量等於跨越到其連接的街道容量1
2. 從每個街道到宿在交叉點上的值
3. 從每個交叉容量爲1的節點

如果構建從源到最大的最大流量，則從交叉點到街道的邊緣流將告訴您如何分配va梅毒。