POJ 2536 Gopher II

問題

n匹のネズミの位置と、m匹のネズミ穴の位置が与えられる。タカがネズミを狙っており、s秒たった時点で穴に隠れていないネズミは捕食される。すべてのネズミは速度vで動くことができ、一つの穴には一匹のネズミだけが隠れることができる。捕食されるネズミの数を最小化せよ。

やりかた

各ネズミと各ネズミ穴の間でs秒以内に到達できるペアに辺を張って、二部グラフを作って二部マッチングすると逃げ切れるネズミの数を最大化できる。

以下ソース。

double gx[100], gy[100], hx[100], hy[100];
vector<vector<int> > G; //bidirection

bool augment(int u, 
	     vector<int> &match, vector<bool> &vis){
  vis[u] = true;
  for(int i = 0; i < G[u].size(); i++){
    int v = G[u][i], w = match[v];
    if(w == -1 || (!vis[w] && augment(w, match, vis))){
      match[u] = v, match[v] = u;
      return true;
    }
  }
  return false;
}

int bipartite_matching(){
  int V = G.size(), ret = 0;
  vector<int> match(V, -1);
  for(int i = 0; i < V; i++){
    if(match[i] != -1) continue;
    vector<bool> vis(V, false);
    if(augment(i, match, vis)) ret++;
  }
  return ret;
}

int main(int argc, char **argv){
  int n, m, s, v;
  while(cin >> n >> m >> s >> v){
    for(int i = 0; i < n; i++) cin >> gx[i] >> gy[i];
    for(int i = 0; i < m; i++) cin >> hx[i] >> hy[i];

    G.clear();
    G.resize(n + m);
    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
	double d = sqrt(pow(gx[i] - hx[j], 2.0) + pow(gy[i] - hy[j], 2.0));
	if(d / v < s){
	  G[i].push_back(n + j);
	  G[n + j].push_back(i);
	}
      }
    }
    cout << n - bipartite_matching() << endl;
  }
  return 0;
}