c# - 递归树算法总结项目的总成本

Question

有没有人有解决这个问题的想法，但只使用通用树？

我需要对所有节点求和，但要尊重边缘值。

如果两个节点之间的边 > 1，则子树的成本最多可乘以整个子树。

解决方案必须使用树算法

谢谢

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

Answer 1

假设您有一个 object 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;
    }
}

您应该调用CostDAG 的源（即没有传入边的节点）。如果您有多个来源，则取决于您想要实现的目标。