AGC039-B Graph Partition
問題概要
n <= 200の頂点を持つ、無向グラフの隣接行列が与えられる。それらの頂点をのk個の集合に分ける。集合
に含まれる頂点は、番号がちょうど一つ前と後の集合、
に含まれる点とすべて辺でつながっていないといけないし、集合
から出てる辺もまたすべて
と連結するのに必要十分でないといけない。このような振り分け方があるのならkを最大化してkを答えよ。ないなら-1を答えよ。
ACするまで
1. AGCのAで事故（2連続）して考える時間が取れなかった。
2. 点の振り分けってことはN部グラフかなー
3. 前後としかつながらなず、ほかの集合とはつながらないって、二部グラフの構造が似てるなぁ
4.二部グラフであれば、すべての頂点が一本道につながらなくても、いい感じに振り分ければなんとかなりそう。
5.二部グラフであることが保証されるのなら、木の直径の両端の点のうちの1つ、
考察
この問題で、まず考え付くべきなのは、
頂点の振り分け、どの集合も前後の集合としか連結しない。
この二つの特徴に当てはまる構造は二部グラフ(の条件を厳しくしたもの)であると経験からでも直感からでもわからないといけない。
二部グラフで、（頂点集合を頂点とみなして、その）頂点番号を以下のように振れば
1 2
3 4
5 6
7 8
etc
頂点番号3は2と4とだけつながりあう、ようにすればよい。
与えられたグラフがいくつかのお互い連結しないグラフによるものだとする。そのうちのグラフの最大の直径をとする。ほかのグラフ２の直径がたとえば、
ならば、
には直径最大のグラフのある始点からの距離1, 2の頂点集合、
以降は直径最大のグラフのある始点からの距離3と、グラフ２から距離1の集合にすればよい。
よって、直径最大のグラフを考える。これが二部グラフであるのならば、直径ならば、
個の集合に振り分けられると示す。
グラフは二部グラフなので、ある点から同じ距離の点の集合はすべて同じ色になる。よって、距離ごとに頂点集合を振り分ければ、条件を満たすものができる(これができないものは、二部グラフではないので)。この時、最大の直径を利用すれば、
個の頂点集合を作れる。
一言
経験不足。精進してない俺が悪い。
以上
