概要
N 個の歯車があり、それぞれの色は赤、緑、青のいずれかである。
噛み合っている歯車どうしは、互いに逆向きにしか回転できない。
また、同じ色の歯車は同じ方向に回らなければならない。
必要があれば、歯車を取り外して空きにすることができる。
（取り外した歯車の両隣の歯車は噛み合わない）
歯車同士がどのように噛み合っているかの情報が与えられる。
同じ色の歯車同士は噛み合っていない。
全ての歯車が回転できるようにするためには、最小でいくつの歯車を取り除く必要があるか求めよ。
解法
まず、色毎にどちら向きに回すかを仮定します。
このとき、全ての色を同じ向きに回すのは無駄が大きいので、一色だけ違う向きに回るようにします。
逆向きに回っている一色については、同色間に辺が無いという制約から、何の問題も無く回転できます。
他の二色について、最大でいくつの歯車が回転できるか考えます。
これは、「互いに噛み合わないように歯車の集合を選ぶ」という操作ですから、独立集合に帰着されます。
集合の要素はできるだけ多くしたいので、最大独立集合です。
今考えている歯車の色は二色で、同色間には辺がありませんから、これは二部グラフです。
蟻本等にも書いてある通り、二部グラフの場合、｜最大マッチング｜＝｜最小点カバー｜ です。
また、｜最大独立集合｜＝ 頂点数 −｜最小点カバー｜ です。
なので、頂点数から最大マッチングの数を引けば最大独立集合の要素数になります。
一色を取り除いて得られる残りの歯車の最大独立集合の最大のサイズを N から引いた値が、取り除かなければなっらない歯車の数です。
コード
typedef vector<string> VS; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define FOR( v, c ) for ( auto &v : c ) // 二部グラフマッチング O( |V||E| ) class BipartiteMatching // 中身省略 // BipartiteMatching( |V| ) // connect( u, v ) // solve() class GearsDiv1 { public: int N; string color; VS G; int getmin( string color, vector <string> graph ) { this -> N = color.size(); this -> color = color; this -> G = graph; int res = 0; FOR( c, "RGB" ) { res = max( res, solve( c ) ); } return N - res; } int solve( char exc ) { BipartiteMatching bm( N ); REP( i, 0, N ) { REP( j, 0, i ) { if ( color[i] == exc || color[j] == exc ) { continue; } if ( G[i][j] == 'Y' ) { bm.connect( i, j ); } } } return N - bm.solve(); } };
