CF1666J.Job Lookup

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 < 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$。如果有多个最优解，输出任意一个即可。

最小可能的通信总成本为 $566 \cdot 1+239 \cdot 1+30 \cdot 1+1 \cdot 2+1 \cdot 2=839$：

由 ChatGPT 4.1 翻译