프로젝트의 총 비용을 합산하는 재귀 트리 알고리즘

Question

누구나이 문제를 해결할 수있는 아이디어가 있습니까?

모든 노드를 합산해야하지만 에지 값을 존중해야합니다.

두 노드 사이의 가장자리가 1보다 큰 경우 하위 트리의 비용이 전체 하위 트리에 대해 대부분 곱 해집니다.

솔루션은 그 자체 cost 나가는 edges 세트는 각각 갖는 무게를 포함하면 객체 Node이 가정

감사

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

Answer 1

을 트리 알고리즘을 사용하고 있어야합니다, 당신 다음을 할 수 있습니다.

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를 호출해야합니다 (당신이 나무가 표시되지 않습니다 게시 된 사진부터 주 나는, pkacprzak 언급대로, DAG를 가지고 가정) 들어오는 가장자리없이). 소스가 여러 개인 경우 원하는 목표에 달려 있습니다.