1
4 3
3
1
2
最优方案为：
总部O以费用为1的方案连接1阁下级中继M,以费用为2，3的方案分别连接2个工事P1,P2
中继M以费用1，2的方案再连接2个工事P3,P4
P1的费用为2
P2的费用为3
P3的费用为1
P4的费用为2
M的费用为1*2=2（由2个下级工事）
最后计算总费用时，因为M有2个直接（或间接）连接的下级工事，所以还需要乘以2（于是2*2=4）
总费用是2+3+1+2+4=12

特别注意！
实际上，如果一个中继有N个下级，而它的上级以费用C方案连接它，那么应该把C*N*N加到总费用中去

• 需要加到hint中吗？ (320) hawk 2004-09-12 12:26:41
  • 需要 (0) rruucc 2004-09-12 12:27:12