25364번 - Job Lookup 다국어

문제

Julia's $n$ friends want to organize a startup in a new country they moved to. They assigned each other numbers from 1 to $n$ according to the jobs they have, from the most front-end tasks to the most back-end ones. They also estimated a matrix $c,ドル where $c_{ij} = c_{ji}$ is the average number of messages per month between people doing jobs $i$ and $j$.

Now they want to make a hierarchy tree. It will be a binary tree with each node containing one member of the team. Some member will be selected as a leader of the team and will be contained in the root node. In order for the leader to be able to easily reach any subordinate, for each node $v$ of the tree, the following should apply: all members in its left subtree must have smaller numbers than $v,ドル and all members in its right subtree must have larger numbers than $v$.

After the hierarchy tree is settled, people doing jobs $i$ and $j$ will be communicating via the shortest path in the tree between their nodes. Let's denote the length of this path as $d_{ij}$. Thus, the cost of their communication is $c_{ij} \cdot d_{ij}$.

Your task is to find a hierarchy tree that minimizes the total cost of communication over all pairs: $\sum_{1 \le i < j \le n} c_{ij} \cdot d_{ij}$.

입력

The first line contains an integer $n$ (1ドル \le n \le 200$) -- the number of team members organizing a startup.

The next $n$ lines contain $n$ integers each, $j$-th number in $i$-th line is $c_{ij}$ --- the estimated number of messages per month between team members $i$ and $j$ (0ドル \le c_{ij} \le 10^9; c_{ij} = c_{ji}; c_{ii} = 0$).

출력

Output a description of a hierarchy tree that minimizes the total cost of communication. To do so, for each team member from 1 to $n$ output the number of the member in its parent node, or 0 for the leader. If there are many optimal trees, output a description of any one of them.

제한

힌트

The minimal possible total cost is 566ドル \cdot 1+239 \cdot 1+30 \cdot 1+1 \cdot 2+1 \cdot 2=839$: