遞歸樹算法總計項目總成本

Question

有沒有人有想法解決這個問題，但只使用通用樹？

我需要對所有節點進行求和，但要考慮邊緣值。

如果兩個節點之間的邊緣大於1，那麼子樹的成本最可能是整個子樹的倍數。

該解決方案必須使用一個樹算法

由於

http://oi39.tinypic.com/24buik7.jpg

Answer 1

假設你有一個對象Node，含有它自己的cost和一組傳出edges，每個具有權重，則可以做到以下幾點。 （注意我假設你有一個DAG，由pkacprzak提到的，由於你發佈不顯示樹的圖片）

class Edge 
{ 
    public int Weight { get; set; } 
    public Node Start { get; set; } 
    public Node End { get set; } 
} 

class Node 
{ 
    private int cost; 
    private IEnumerable<Edge> edges; 

    // ... 

    public int Cost() 
    { 
     int totalCost = cost; 

     foreach (var edge in edges) 
     { 
      totalCost += edge.Weight * edge.End.Cost(); 
     } 

     return totalCost; 
    } 
} 

您應該將DAG的來源（即在節點上調用Cost沒有傳入邊緣）。如果您有多個來源，則取決於您想要達到的目標。