TopCoder SRM 531 Div2 Hard KingdomReorganization

これは割とすんなり。
http://community.topcoder.com/stat?c=problem_statement&pm=11282

問題

N個の都市があり、一部の都市同士は無向辺で接続されている。
一部の都市は互いに接続されておらず、また都市同士をつなぐ経路が複数ある場合がある。
ここから一部の辺を削除し、また一部の辺を追加して全ての都市が１つの木を成すようにしたい。

各都市間における辺追加および辺削除のコストが与えられるとき、条件を満たす最小コストを求めよ。

解法

複数経路出来る辺の削除と、未接続都市の接続をそれぞれ行い、コストの和を取ればよい。

前者は、もともと連結されている都市間において、削除コストの高い順にクラスカル法の要領で全域木を作り、全辺削除コストから全域木を構築する辺の削除コストを引けばよい。

後者は、もともと未接続な都市群同士を追加コストの低い順にクラスカル法の要領で全域木を作ればよい。

以下のコードではともにUnion-find法で連結された都市を管理した。

class UF {
	public:
	static const int ufmax=502;
	int ufpar[ufmax],ufrank[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y;
		else {ufpar[y]=x; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

class KingdomReorganization {
	vector<string> K;
	int B[51][51],D[51][51];
	int N;
	UF duf;
	
	public:
	int prune(int cur) {
		int x,y,r=0;
		FOR(x,N) FOR(y,N) if(duf[x]==cur && K[x][y]=='1' && x<y) r+=D[x][y];
		UF uf;
		
		while(1) {
			int ma=-1;
			int ne=-1;
			
			FOR(x,N) FOR(y,N) if(uf[x]==uf[cur] && uf[y]!=uf[cur] && K[x][y]=='1') {
				if(ma < D[x][y]) ma=D[x][y], ne=y;
			}
			if(ne==-1) break;
			r -= ma;
			uf.unite(ne,cur);
		}
		return r;
	}
	
	int getCost(vector <string> kingdom, vector <string> build, vector <string> destroy) {
		K=kingdom;
		N=K.size();
		int x,y,r=0;
		
		duf.init();
		FOR(x,N) FOR(y,N) {
			if(build[x][y]>='a') B[x][y]=build[x][y]-'a'+26;
			else B[x][y]=(build[x][y]-'A');
			if(destroy[x][y]>='a') D[x][y]=destroy[x][y]-'a'+26;
			else D[x][y]=(destroy[x][y]-'A');
		}
		FOR(x,N) FOR(y,N) if(K[x][y]=='1') duf.unite(x,y);
		FOR(x,N) if(duf[x]==x) r+=prune(x);
		
		while(1) {
			int mi=10000;
			int ne=-1;
			
			FOR(x,N) FOR(y,N) if(duf[x]==duf[0] && duf[y]!=duf[0]){
				if(mi>B[x][y]) mi=B[x][y], ne=y;
			}
			
			if(ne==-1) return r;
			r+=mi;
			duf.unite(0,ne);
		}
		return r;
		
	}
};

まとめ

クラスカル法の復習として手頃な問題でした。