M-SOLUTIONS プロコンオープン：D - Maximum Sum of Minimum
問題
解法
まず c を降順にソートする．ある頂点に c_1 を置いたとき，この頂点に隣り合う頂点に書く数字は c_2, c_3, ... とするのがよい．なぜならば，あえて小さい整数を最初に選んだ頂点に近づけても (c_1 - (小さい整数)) だけ「損失」が出てしまうから．それだったら出来るだけ c_1 に近い整数を隣接する頂点に書いていった方が，隣接する頂点に書いた数が c_1 との辺に書かれる数となり，これらの数は最大となる．これは最初に選んだ頂点から BFS をすることで整数を頂点に割り振っていくことが出来る．O(NlogN)．
解答
