kmjp's blog

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

TopCoderOpen 2020 South Asia : Hard BridgesAndCutVertices

意外に悩んだ。
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;
		
	}
}

まとめ

地味に「橋を作らずに関節点を増やすには?」で手間取った。