AOJ2306 Rabbit Party

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2306
2011年のJAG夏合宿問題らしい。出題者の解説スライドなど

入力：
n匹のウサギと、そのウサギmペアの仲良し度が与えられる。仲良しじゃないペアは仲良し度0とする。
つまり
n頂点完全無向グラフ$(V,E)$上のm辺の重み$f{:}  E  \to \mathbb{N}$が与えられる。重みが与えられない辺は重み0と見なす。

出力：
それぞれのウサギの幸せ度はパーティーに参加している他の参加者との仲良し度の最小値。もし仲良し度0の相手がいると自分も相手も幸せ度0になる。コワイ！
参加者の幸せ度の総和が最大になるように参加者を選んで、幸せ度の総和を出力せよ
つまり
\begin{align*}
    \max_{S\subset V} \left\{ \sum_{v\in S} \min\left\{ f(\left\{u,v\right\}) | u \in S , u \neq v\right\} \right\}
\end{align*}

制約：
\begin{align*}
1 \leq &n \leq 100 \\
0 \leq &m \leq 100 \\
1 \leq f&(e) \leq 1,000,000 \ \ (\forall e \in E )
\end{align*}

考察：
もし選んだ頂点からなるクリークが重みゼロの辺を含むとすると、その両端の幸せ度は0
どちらかを外した方がマシになるので、最適解のクリークは辺の重みが全部非ゼロ。重みが非ゼロの辺の本数が100しかないので、最適解の頂点集合の大きさは高々14。
という数学的事実があるがここでは無視する。

手順：
すべての重みが非ゼロの辺 $e \in E$に対して次の貪欲アルゴリズムを適用し、その最大値を求める。
1. eの端点2つを参加者の集合Sに入れる。
2. $V-S$の中で、$S \bigcup \{ v \}$の幸せ度の総和が最大となるような参加者v*を探す
3. Sにv*を追加したときに幸せ度の総和が増加するならSにv*を追加し、Step2に戻る。
4. 追加して幸せ度が増加するようなvがなくなったら終了し、幸せ度の総和を返す。
計算量は$\mathrm{O}(mn(m+n))$かな？

実装：

感想：
間違っている気がするけれど、ACしたし、間違っていることを証明することもできなかったし、よく分からない