SRM 531 Div2 Hard KingdomReorganization

http://community.topcoder.com/stat?c=problem_statement&pm=11282

問題

王国にはNの街があり、街と街の間がつながっているかがkingdom[i][j]で与えられる。また、街と街の間に新たに道路を作る費用がbuild[i][j]で、道路を壊す費用がdestroy[i][j]で与えられる。この状態から街を作るなり、壊すなりしてある街からある街までいく方法が必ず1通りのみになるようにしたい。この様にするための最小の費用を求めよ。

やりかた

もともと道路がないところでは道路を壊しようがないので作るだけ、道路がある所では新たに作りようがないので壊すだけ。

あらかじめ閉路をなしている街があったとき、どの辺を壊さないほうがコストが低いかについて考える。これは存在する辺の破壊コストをまずすべて足しておき、そこから存在する辺の破壊コストをマイナスしたものをコストとしたグラフの最小全域木にするコストを引けばいい。するとこれは閉路を壊すためにもっとも最小の費用を返す。下図参照。

あとは辺を張るべきところの話なので通常の最小全域木となる。

以下ソース。

class KingdomReorganization {
public:
  int prim(vector<vector<int> > dist){
    int N = dist.size();
    vector<bool> used(N, false);
    int ret = 0;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q;
    Q.push(make_pair(0, 0));
    while(!Q.empty()){
      int 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; i++) Q.push(make_pair(dist[to][i], i));
    }
    return ret;
  }

  int getCost(vector <string> kingdom, vector <string> build, vector <string> destroy) {
    int result;
    int N = kingdom.size();
    vector<vector<int> > b(N, vector<int>(N, 0));
    vector<vector<int> > d(N, vector<int>(N, 0));

    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
	if(build[i][j] <= 'Z') b[i][j] = build[i][j] - 'A';
	else b[i][j] = build[i][j] - 'a' + 26;
	if(destroy[i][j] <= 'Z') d[i][j] = destroy[i][j] - 'A';
	else d[i][j] = destroy[i][j] - 'a' + 26;
      }
    }

    int ans = 0;
    vector<vector<int> > con(N, vector<int>(N, 0));
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++)
	if(kingdom[i][j] == '1')
	  con[i][j] = -d[i][j];
	else 
	  con[i][j] = b[i][j];

    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++)
	if(kingdom[i][j] == '1') ans += d[i][j];

    cout << ans << " " << prim(con) << endl;
    return ans / 2 + prim(con);
  }
};
<<