yukicoder : No.466 ジオラマ

構築ゲーは苦手。
http://yukicoder.me/problems/no/466

問題

パラメータA,B,C,Dが与えられる。
以下の条件を満たすグラフを作成可能なら、その例を示せ。

• 0～(N-1)番のN頂点M辺からなる有向グラフである。
• MはD以下である。
• 0番の頂点から有向辺をたどり到達可能な頂点はA個
• 1番の頂点から有向辺をたどり到達可能な頂点はB個
• 0番、1番の頂点から有向辺をたどり、どちらからも到達可能な頂点はC個
• 0番、1番の頂点から有向辺をたどり、どちらからも到達不可能な頂点はない

解法

到達可能な頂点数を満たす最少辺のグラフを作ろう。
以下A,B,Cの関係によりグラフの形状が変わる。

• A==B==Cの場合：
  • A==B==C==1なら解なし。
  • A==B==C＞1の場合、A個の頂点で閉路を作ればよい。
• A==CまたはB==Cの場合
  • 以下A==C、B＞Cの場合を示す。B個の頂点を1列に並べて端から順に有向辺で結ぶ。最初の頂点を1番、末尾から数えてA個目の頂点を0番にすればよい。
• C==0の場合
  • 0番に(A-1)個、1番に(B-1)個の頂点をぶら下げればよい。
• それ以外(A＞C、B＞C、C!=0)
  • まずC個の頂点を１列につなげる。0番、1番の頂点からその根元の頂点に辺を張る。
  • あとは残り、0番からつながる(A-(C+1))個の頂点を追加し、1番からつながる(B-(C+1))個の頂点を追加すればよい。

int A,B,C,D;

vector<pair<int,int>> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C>>D;
	if(A==C && B==C) {
		if(A==1) return _P("-1\n");
		FOR(i,A) V.push_back({i,(i+1)%A});
	}
	else if(A==C) {
		x=1,y=2;
		FOR(i,B-A-1) V.push_back({x,y}),x=y++;
		V.push_back({x,0});
		x=0;
		FOR(i,A-1) V.push_back({x,y}),x=y++;
	}
	else if(B==C) {
		x=0,y=2;
		FOR(i,A-B-1) V.push_back({x,y}),x=y++;
		V.push_back({x,1});
		x=1;
		FOR(i,B-1) V.push_back({x,y}),x=y++;
	}
	else if(C==0) {
		x=2;
		FOR(i,A-1) V.push_back({0,x++});
		FOR(i,B-1) V.push_back({1,x++});
	}
	else {
		V.push_back({0,2});
		V.push_back({1,2});
		x=2,y=3;
		FOR(i,C-1) V.push_back({x,y}),x=y++;
		x=y;
		FOR(i,A-(C+1)) V.push_back({0,x++});
		FOR(i,B-(C+1)) V.push_back({1,x++});
	}
	
	if(V.size()>D) _P("-1\n");
	else {
		int ma=1;
		FORR(v,V) ma=max(ma,max(v.first,v.second));
		_P("%d %d\n",ma+1,V.size());
		FORR(v,V) _P("%d %d\n",v.first,v.second);
	}
}

まとめ

なぜジオラマというタイトルにしたんだろう…。