Codeforces #896 : Div1 D. Flower-like Pseudotree

シンプルな問題設定。
https://codeforces.com/contest/1868/problem/D

問題

N点の無向グラフを考える。
各点の次数が与えられるので、それを満たす連結なN辺のいわゆるなもりグラフが作れるか。
可能なら一例を示せ。なお、多重辺があってもよい。

解法

次数の総和が2Nでなければならない。
もし全点次数が2なら、全体で閉路を1個作ればよい。
そうでない場合、次数を降順にソートすると上位2つは3以上でなければならない。

次数1の点は後で適当につなげるとして、次数1以外の点をどうするか考える。
次数を降順にソート済みだとしたら、0番と1番の点に二重辺を張る。
これで1個閉路ができたので、あとはそこに次数2以上の辺を連結し、(最初の二重辺を除いて)木になるようにしていく。
最後に、次数1の点を適当にくっ付けよう。

int T,N,D[1010101];

vector<pair<int,int>> V;
void out(int a,int b) {
	a%=N;
	b%=N;
	V[a].first--;
	V[b].first--;
	cout<<(V[a].second%N)+1<<" "<<(V[b].second%N)+1<<"\n";
}

void go(int C) {
	int i;
	int x=C;
	FOR(i,C) while(V[i].first) {
		out(i,x);
		x++;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&N);
		ll sum=0;
		V.clear();
		FOR(i,N) {
			scanf("%d",&D[i]);
			sum+=D[i];
			V.push_back({D[i],i});
		}
		if(sum!=2*N) {
			cout<<"NO"<<"\n";
			continue;
		}
		int C=N;
		sort(ALL(V));
		reverse(ALL(V));
		while(V[C-1].first==1) C--;
		
		if(V[0].first==2) {
			cout<<"YES"<<"\n";
			FOR(i,N) out(i,i+1);
			continue;
		}
		if(V[1].first==2) {
			cout<<"NO"<<"\n";
			continue;
		}
		if(C%2==0) {
			cout<<"YES"<<"\n";
			out(0,1);
			out(0,1);
			for(i=2;i<C;i+=2) {
				out(i-2,i);
				out(i-1,i+1);
			}
			go(C);
			continue;
		}
		if(C%2&&V[0].first>3&&C>=5) {
			cout<<"YES"<<"\n";
			out(0,1);
			out(0,1);
			out(0,2);
			out(0,3);
			out(1,4);
			for(i=5;i<C;i+=2) {
				out(i-2,i);
				out(i-1,i+1);
			}
			go(C);
			continue;
		}
		if(C%2&&V[0].first>3&&C==3) {
			if(V[2].first<=2) {
				cout<<"NO"<<"\n";
				continue;
			}
			cout<<"YES"<<"\n";
			out(0,1);
			out(1,2);
			out(2,0);
			go(3);
			continue;
		}
		if(C%2&&V[0].first==3&&V[2].first>=3&&C>=7) {
			cout<<"YES"<<"\n";
			out(0,1);
			out(0,1);
			out(0,2);
			out(1,3);
			out(2,4);
			out(2,5);
			out(3,6);
			for(i=7;i<C;i+=2) {
				out(i-2,i);
				out(i-1,i+1);
			}
			go(C);
			continue;
		}
		if(C==5&&V[0].first==3&&V[4].first==3) {
			cout<<"YES"<<"\n";
			out(0,1);
			out(1,2);
			out(2,3);
			out(3,4);
			out(4,0);
			go(5);
			continue;
		}
		if(C==3&&V[0].first==3&&V[2].first==3) {
			cout<<"YES"<<"\n";
			out(0,1);
			out(1,2);
			out(2,0);
			go(3);
			continue;
		}
		cout<<"NO"<<"\n";
		
	}
}

まとめ

だいぶ端折ったけど、これ場合分けかなりめんどいな。