Div2 Mediumということで割とあっさり。
http://community.topcoder.com/stat?c=problem_statement&pm=13546
問題
N個のノードが2組ある。
各組のノードは横1列に並んでおり、隣接ノードには無向辺が張られておりそのコストが与えられる。
ここで、これらのノードに橋を渡したい。
各橋は片方の組のi番目のノードともう片方の組のi番目のノードをつなぐコスト0の無向辺となる。
橋をK本まで掛けられるとき、このグラフの直径を最小化せよ。
解法
この問題はNが11未満と小さい。
よって橋のかけ方を通り総当たりすればよい。
直径算出は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; } }
まとめ
一見めんどくさそうで結構あっさり書けたな。