【Codeforces 639B】Bear and Forgotten Tree 3

Zarxdy34 posted @ 2016年4月06日 16:48 in Codeforces with tags 坑题 , 199 阅读

  这题难度不大,但是细节比较多。

  先不考虑无解的情况,从1到h+1造一条链,为树高;然后再连一条1到h+2的边,从h+2到d+1造一条链,这样造出了树直径。然后为剩下的点找个中心点造个菊花图就好了。

  可以得到,只有d=1或者h*2<d的时候是无解的。如果d>h的话,菊花图的中心选1;如果d==h的话,菊花图的中心选2。

 

#include <cstdio>
#include <cstring>
using namespace std;

int n,d,h;

int main()
{
	scanf("%d%d%d",&n,&d,&h);
	if (h*2<d || (n>2 && d==1)) {printf("-1\n");return 0;}
	for (int i=2;i<=h+1;i++) printf("%d %d\n",i-1,i);
	if (d==h)
	{
		for (int i=h+2;i<=n;i++) printf("2 %d\n",i);
		return 0;
	}
	printf("1 %d\n",h+2);
	for (int i=h+3;i<=d+1;i++) printf("%d %d\n",i-1,i);
	for (int i=d+2;i<=n;i++) printf("%d %d\n",1,i);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1