SRM 303 Div1 Medium Knights

問題

NxNのチェスボード上にいくつかのナイトが置かれておりそれらの位置がposで与えられる。（表記の仕方は問題文参照）
任意のナイトを一回だけ移動した時に、移動先に別のナイトがいないようにしたい。取り除かねばならない最小のナイトの数を求めよ。

やりかた

各ナイトをグラフのノードとして、ぶつかりあうような位置関係にあるナイトをエッジで結んだ無向グラフを考えた場合、どのナイトもぶつかり合わない状態というのは、このグラフの最大安定集合を求めることと同じになる。ナイトの動きというのは必ずチェスボード上の白から黒のマス、もしくは黒から白のマスへの移動となるから、このグラフは必ず二部グラフになる。グラフ理論では|最大安定集合|=頂点数 - |最小点カバー|が成立し、特に二部グラフでは|最小点カバー|=最大マッチング数となるので、最大流のアルゴリズムを使って効率的に最大安定集合を求めることができる。
今回は取り除く数を求める問題なので、最小点カバー数を求めれば良い。

以下ソース。二部マッチングの部分は蟻本のP197のコードを使用。（ただし９行目をコメントアウト）

int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};

int V; // 頂点数
const int MAX_V = 2000;

class Knights {
public:
  int s2i(string s){
    stringstream ss(s);
    int x; ss >> x; return x;
  }
  int makeFriendly(int N, vector <string> pos){
    for(int i = 0; i < MAX_V; i++) G[i].clear();

    V = 0;
    vector<pair<int, int>> p;
    vector<vector<bool>> vis(N, vector<bool>(N, false));
    for(int i = 0; i < (int)pos.size(); i++){ //ナイトの位置をデコード
      stringstream ss(pos[i]); string s;
      while(ss >> s){
	V++;
	int y = s[0] - 'A', x = s2i(s.substr(1)) - 1;
	p.push_back(make_pair(y, x));
	vis[y][x] = true;
      }
    }
    
    //ナイトがぶつかりあうような関係をエッジにして結ぶ
    for(int k = 0; k < V; k++){
      int y = p[k].first, x = p[k].second;
      for(int i = 0; i < 8; i++){
	if(0 <= y + dy[i] && y + dy[i] < N && 
	   0 <= x + dx[i] && x + dx[i] < N && 
	   vis[y + dy[i]][x + dx[i]]){
	  int idx = find(ALL(p), 
			 make_pair(y + dy[i], x + dx[i])) - p.begin();
	  add_edge(k, idx);
	}
      }
    }
    return bipartite_matching();
  }
};