# AHC017

どう考えてもまともな貪欲が必要だけど，グラフを分割するのがめんどくさすぎる
絶対スコアが低いほうが良い相対スコアが出て？？？になってたらそういうコンテストだった カス

## 最終解
* u→vへの最短パスを取り除く
~~* 最短パスと同じ辺数の迂回路？~~
* 閉路ができるとだめ
* 次数分辺を生やすとだめ
* 隣の道を同じ日に取るとスコアが下がりやすい
* 最初に道を作ってから割り振る←やってない
* 縦の道と横の道
* 外周から剥いでいく

## 案

* クラスタ内の辺の中心座標間の距離のminの最大化
* 中心座標じゃなくてグラフ上の距離にする
* 一番遠いところに割り振る貪欲をやる
* 辺を座標 m / d 分割して各クラスタから1日1つ
* nとdを軸にプロットして初期値と比較する
* MSTを取ってそれ以外を削除
* 割当が難しい
* MST を d区画に分けて削除
* mst を削除する区画はそれ以外を残す
* ランダムな木を除外

## 最悪のパターン
ｷﾚｲﾀﾞﾅｰ

## 最高のパターン
焼きなましを24時間を回した
どう考えても木を取り除いている気がするが，なんでこれがいいんや
木というか最短パスを取り除いてるっぽい？