prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem G:</font> Network Mess</H1>3 4<p>5Gilbert is the network admin of Ginkgo company. His boss is mad about the messy network6cables on the floor. He finally walked up to Gilbert and asked the lazy network admin to illustrate7how computers and switches are connected. Since he is a programmer, he is very reluctant to8move throughout the office and examine cables and switches with his eyes. He instead opted9to get this job done by measurement and a little bit of mathematical thinking, sitting down in10front of his computer all the time. Your job is to help him by writing a program to reconstruct11the network topology from measurements.12</p>13<p>14There are a known number of computers and an unknown number of switches. Each computer15is connected to one of the switches via a cable and to nothing else. Specifically, a computer16is never connected to another computer directly, or never connected to two or more switches.17Switches are connected via cables to form a tree (a connected undirected graph with no cycles).18No switches are ‘useless.’ In other words, each switch is on the path between at least one pair19of computers.20</p>21<p>22All in all, computers and switches together form a tree whose leaves are computers and whose23internal nodes switches (See Figure 9).24</p>25<p>26Gilbert measures the distances between <i>all pairs of computers</i>. The distance between two com-27puters is simply the number of switches on the path between the two, plus one. Or equivalently,28it is the number of cables used to connect them. You may wonder how Gilbert can actually29obtain these distances solely based on measurement. Well, he can do so by a very sophisticated30statistical processing technique he invented. Please do not ask the details.31</p>32<p>33You are therefore given a matrix describing distances between leaves of a tree. Your job is to34construct the tree from it.35</p>36 37<H2>Input</H2>38 39<p>40The input is a series of distance matrices, followed by a line consisting of a single '<span>0</span>'. Each41distance matrix is formatted as follows.42</p>43 44<pre>45<i>N</i>46<i>a</i><sub>11</sub> <i>a</i><sub>12</sub>  ...   <i>a</i><sub>1<i>N</i></sub>47<i>a</i><sub>21</sub> <i>a</i><sub>22</sub>  ...   <i>a</i><sub>2<i>N</i></sub>48 .   .  .      .49 .   .    .    .50 .   .      .  .51<i>a</i><sub><i>N</i>1</sub> <i>a</i><sub><i>N</i>2</sub>  ...   <i>a</i><sub><i>N</i><i>N</i></sub>52 53</pre>54 55<br>56<center>57<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_networkMess">58</center>59<br>60 61<p>62<i>N</i> is the size, i.e. the number of rows and the number of columns, of the matrix. <i>a<sub>ij</sub></i> gives the63distance between the <i>i</i>-th leaf node (computer) and the <i>j</i>-th. You may assume 2 &le; <i>N</i> &le; 50 and64the matrix is symmetric whose diagonal elements are all zeros. That is, <i>a<sub>ii</sub></i> = 0 and <i>a<sub>ij</sub></i> = <i>a<sub>ji</sub></i>65for each <i>i</i> and <i>j</i>. Each non-diagonal element <i>a<sub>ij</sub></i> (<i>i</i> &ne; <i>j</i>) satisfies 2 &le; <i>a<sub>ij</sub></i> &le; 30. You may assume66there is always a solution. That is, there is a tree having the given distances between leaf nodes.67 68</p>69 70 71<H2>Output</H2>72 73<p>74For each distance matrix, find a tree having the given distances between leaf nodes. Then output75the degree of each internal node (i.e. the number of cables adjoining each switch), all in a single76line and in ascending order. Numbers in a line should be separated by a single space. A line77should not contain any other characters, including trailing spaces.78 79</p>80 81<H2>Sample Input</H2>82<pre>83484   0  2  2  285   2  0  2  286   2  2  0  287   2  2  2  088489   0  2  4  490   2  0  4  491   4  4  0  292   4  4  2  093294   0 1295  12  096097</pre>98 99<H2>Output for the Sample Input</H2>100<pre>10141022 3 31032 2 2 2 2 2 2 2 2 2 2104</pre>105 106 107 108 109