Julia 的 $$$n$$$ 朋友想要在他们搬到的新国家组织一家初创公司。他们根据自己的工作,从最前端的任务到最后端的任务,为彼此分配从 1 到 $$$n$$$ 的编号。他们还估计了一个矩阵 $$$c$$$,其中 $$$c_{ij} = c_{ji}$$$ 是从事 $$$i$$$ 工作和 $$$j$$$ 工作的人员之间每月平均消息数。
现在他们想要制作一个层次结构树。这将是一个 二叉树 每个节点包含一名团队成员。一些成员将被选为团队的领导者并包含在根节点中。为了使领导者能够轻松地到达任何下属,对于树的每个节点$$$v$$$,应适用以下规则:其左子树中的所有成员的数字必须小于$$$v$$$,其右子树中的所有成员的数字必须大于$$$v$$$。
层次结构树确定后,从事 $$$i$$$ 和 $$$j$$$ 工作的人员将通过树中节点之间的最短路径进行通信。我们将该路径的长度表示为 $$$d_{ij}$$$。因此,他们的通信成本为 $$$c_{ij} \cdot d_{ij}$$$。
你的任务是找到一个层次结构树,使所有对的通信总成本最小化:$$$\sum_{1 \le i \lt j \le n} c_{ij} \cdot d_{ij}$$$。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200$$$) – 组织初创公司的团队成员数量。
接下来的 $$$n$$$ 行每行包含 $$$n$$$ 个整数,$$$i$$$ 行中的第 $$$j$$$ 个数字是 $$$c_{ij}$$$ - 团队成员 $$$i$$$ 和 $$$j$$$ 之间每月估计的消息数量 ($$$0 \le c_{ij} \le 10^9; c_{ij} = c_{ji}; c_{ii} = 0$$$)。
输出
输出层次结构树的描述,使通信总成本最小化。为此,对于从 1 到 $$$n$$$ 的每个团队成员,输出其父节点中的成员编号,或 0 表示领导者。如果有许多最优树,则输出其中任何一棵的描述。
示例
输入复制
4 0 566 1 0 566 0 239 30 1 239 0 1 0 30 1 0
输出复制
2 4 2 0
注意
最小可能的总成本为 $$$566 \cdot 1+239 \cdot 1+30 \cdot 1+1 \cdot 2+1 \cdot 2=839$$$: