← 返回题目列表

Codeforces · 1666/J

J. 工作查找

中文机器翻译题面 查看原题

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$$$: