意外に悩んだ。
https://community.topcoder.com/stat?c=problem_statement&pm=16321&rd=18116
問題
0以上23以下の整数値B,Cが与えられる。
50頂点・200辺以下の無向グラフで、橋がB本、間接点がC本のグラフを構築せよ。
解法
以下を基本要素とする。
- Bだけを増やしたい場合、1点を中心にそこからB辺を生やせばよい。ただしこの場合B=2以上では中心は関節点になる。
- Cだけを増やしたい場合、三角形を作って、そこから1点を共通する三角形を鎖状につなげていけば2点で1個関節点を作れる。
- BもCも増やしたい場合、点を直列に並べて辺で結べば、1点について橋と関節点を1個つくれる。
あとは場合分けして上記を組み合わせていこう。
- C=0の場合
- 関節点を作りたくないので、2B個の頂点からB個の対を作り、それらの間をB本結ぼう。
- C>0の場合
- まず三角形を1個作る。
- その1点から、min(B,C)個だけ直列で点をつないでいこう。
- B>Cの時、三角形のうち直列の点がつながっている点を選び、そこから追加で(B-C)辺を未使用の点に向かって生やす。
- C>Bの時、三角形のうち直列の点がつながっていない点を選び、そこから追加でC個三角形をつなげていこう。
class BridgesAndCutVertices { public: vector <int> construct(int B, int C) { vector<int> R; int i; if(C==0) { FOR(i,B) { R.push_back(i*2); R.push_back(i*2+1); } } else { int com=min(B,C); B-=com; C-=com; if(B==0) { int cur=0; while(C>=0) { C--; R.push_back(cur); R.push_back(cur+1); R.push_back(cur); R.push_back(cur+2); R.push_back(cur+1); R.push_back(cur+2); cur+=2; } } else { FOR(i,B) { R.push_back(i); R.push_back(B+2); } R.push_back(B); R.push_back(B+1); R.push_back(B); R.push_back(B+2); R.push_back(B+1); R.push_back(B+2); } while(com--) { R.push_back(R.back()); R.push_back(R.back()+1); } } return R; } }
まとめ
地味に「橋を作らずに関節点を増やすには?」で手間取った。