SRM 503 Div2 Hard KingdomXCitiesandVillagesAnother

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10835&rd=14432

街と村が存在し、それらの位置が与えられる。最初、村には道が通っていない。街と村の間に道路を引くか、街に行くことのできる村とそうでない村の間に道路を引くことでどの村も少なくとも一つの街に行けるようにしたい。道路敷設のコストは端と端との間のユークリッド距離である。コストを最小化せよ。

やりかた

普通に最小全域木すればいいような気もするが、街と街の間はつなぐ必要がないので工夫する必要がある。といっても街と街のあいだのコストを0にすればいいだけ。

以下ソース。

class KingdomXCitiesandVillagesAnother {
public:
  double determineLength(vector <int> cityX, vector <int> cityY, vector <int> villageX, vector <int> villageY) {
    int N = cityX.size(), M = villageX.size();
    vector<int> x, y;
    for(int i = 0; i < N; i++) x.push_back(cityX[i]), y.push_back(cityY[i]);
    for(int i = 0; i < M; i++) x.push_back(villageX[i]), y.push_back(villageY[i]);

    vector<vector<double> > dist(N + M, vector<double>(N + M, 0));
    vector<bool> used(N + M, false);
    for(int i = 0; i < N + M; i++) 
      for(int j = 0; j < N + M; j++)
	if(!(i < N && j < N)) dist[i][j] = hypot(x[i] - x[j], y[i] - y[j]);

    double ret = 0;
    priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > Q;
    Q.push(make_pair(0, 0));
    while(!Q.empty()){
      double cost = Q.top().first;
      int to = Q.top().second;
      Q.pop();
      if(used[to]) continue;
      used[to] = true;
      ret += cost;
      for(int i = 0; i < N + M; i++) Q.push(make_pair(dist[to][i], i));
    }
    return ret;
  }
};

まあでも、思いつかなかったんだけどね。