TopCoder SRM 531 Div2 Hard KingdomReorganization

問題

n個の都市からなる国があり、それぞれの都市はいくつかの双方向に通行可能な道路で結ばれている。
kingdom[i][j]が'1'のときiとjは道路で結ばれている。


いま道路を好きなだけつなぐまたは壊して、
任意の二つの都市間にパスが一つだけ存在するようにしたい。


それぞれの道路を作るコスト、壊すコストが与えられるとき、
必要なコストの合計の最小値を求めよ。

制約条件

n≦50
道路は対称。
作るコストはそれぞれ51以下
壊すコストはそれぞれ51以下

方針

グラフが連結になるように、コストの小さい辺から貪欲に足す。
これはPrim法と同じことをすればいい。


その後、余分な辺を削除する。
これは、コストが小さい辺から貪欲に、辺を削除してみて、それでもグラフが連結だったらその辺を削除し、そうでなかったらその辺を残すということをすればいい。

ソースコード

struct KingdomReorganization{
	int getCost(vector<string> kingdom, vector<string> build, vector<string> destroy){
		road=kingdom;
		n=road.size();
		rep(i,n)p[i]=i;
		rep(i,n)rep(j,n)if(road[i][j]=='1'){
			int x=root(i), y=root(j);
			if(x!=y)p[y]=x;
		}
		
		vector<pair<int,pair<int,int> > > b, d;
		rep(i,n)rep(j,n){
			b.push_back(make_pair(cost(build[i][j]), make_pair(i, j)));
			d.push_back(make_pair(cost(destroy[i][j]), make_pair(i, j)));
		}
		sort(b.begin(), b.end());
		sort(d.begin(), d.end());
		
		int ans=0;
		
		rep(i,b.size()){
			int x=b[i].second.first, y=b[i].second.second;
			if(root(x)==root(y))continue;
			road[x][y]=road[y][x]='1';
			x=root(x); y=root(y);
			p[y]=x;
			ans+=b[i].first;
		}
		rep(i,d.size()){
			int x=d[i].second.first, y=d[i].second.second;
			if(road[x][y]=='0')continue;
			road[x][y]=road[y][x]='0';
			if(ck()){
				ans+=d[i].first;
			}
			else{
				road[x][y]=road[y][x]='1';
			}
		}
		return ans;
	}
	vector<string> road;
	int n,p[50];
	int root(int x){
		if(x==p[x])return x;
		return root(p[x]);
	}
	bool ck(){
		rep(i,n)p[i]=i;
		rep(i,n)rep(j,n)if(road[i][j]=='1'){
			int x=root(i), y=root(j);
			if(x!=y)p[y]=x;
		}
		rep(i,n)rep(j,n)if(root(i)!=root(j))return 0;
		return 1;
	}
	int cost(char c){
		if('A'<=c&&c<='Z')return c-'A';
		return c-'a'+26;
	}
};