kmjp's blog

競技プログラミング参加記です

TopCoder SRM 661 Div2 Medium BridgeBuildingDiv2

Div2 Mediumということで割とあっさり。
http://community.topcoder.com/stat?c=problem_statement&pm=13546

問題

N個のノードが2組ある。
各組のノードは横1列に並んでおり、隣接ノードには無向辺が張られておりそのコストが与えられる。

ここで、これらのノードに橋を渡したい。
各橋は片方の組のi番目のノードともう片方の組のi番目のノードをつなぐコスト0の無向辺となる。

橋をK本まで掛けられるとき、このグラフの直径を最小化せよ。

解法

この問題はNが11未満と小さい。
よって橋のかけ方を {}_N C_K通り総当たりすればよい。
直径算出はWarshall-Floyd法を毎回行っても十分間に合う。

int mat[22][22];
class BridgeBuildingDiv2 {
	public:
	
	int minDiameter(vector <int> a, vector <int> b, int K) {
		int N=a.size()+1;
		int mi=101010;
		int i,x,y;
		
		for(int mask=0;mask<1<<N;mask++) if(__builtin_popcount(mask)==K) {
			FOR(x,2*N) FOR(y,2*N) mat[x][y]=(x==y)?0:10101010;
			FOR(x,N-1) mat[x][x+1]=mat[x+1][x]=a[x];
			FOR(x,N-1) mat[N+x][N+x+1]=mat[N+x+1][N+x]=b[x];
			FOR(i,N) if(mask&(1<<i)) mat[i][i+N]=mat[i+N][i]=0;
			
			FOR(i,2*N) FOR(x,2*N) FOR(y,2*N) mat[x][y]=min(mat[x][y],mat[x][i]+mat[i][y]);
			int ma=0;
			FOR(x,2*N) FOR(y,2*N) ma=max(ma,mat[x][y]);
			mi=min(mi,ma);
		}
		return mi;
	}
}

まとめ

一見めんどくさそうで結構あっさり書けたな。