Алгоритм рекурсивного дерева для суммирования общей стоимости проекта

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; 
    } 
} 

Вы должны вызвать Cost на источник вашей DAG (то есть, узел без входящих ребер). Если у вас есть несколько источников, зависит от вас, чего вы хотите достичь.