CodeForces 1003E Tree Constructing

题目

◇题目传送门◆

大意

给定$N$，$D$，$K$，要求构造一棵拥有$N$个节点，直径为$D$，每个节点度数不超过$K$的树。若存在这样的树，则输出“YES”和任意一种边的方案，否则输出“NO”。

思路

我们先来讨论一下特殊情况：

1. $N \leq D$时：我们连一条长度为$D$的链都构造不了，故应输出NO；
2. $D>1$且$K<2$时：极易说明该情况不成立。

注意：有读者反映，当$D>1$且$K<2$时，可以构造成一条链。这里说明为什么该情况不成立：若形成一条链，则中间（即除掉头和尾）的点的度都是2，与条件相矛盾，故该种情况不成立。

接着就是一般情况。

我们考虑先使用编号为$1$至$D+1$节点构造一条长度为$D$的链，则我们可以这条链中的所有距离节点$1$距离为$i$的节点$t$（不包括首尾），求得以$t$为根可以加入的最大深度：$min( i-1,D-i+1)$（极易说明），并利用DFS求出可加入节点的数量及边，即可得出答案。

实现细节

注意：最后输出时，可能存在已使用节点数量小于给定的NN<script type="math/tex" id="MathJax-Element-21">N</script>的情况，这时我们应输出“NO”。

正解代码

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int,int> > ans;
int N,D,K;
int d;void DFS(int u,int dep,int maxd) {if(dep==maxd)return;for(int i=0;i<K-1-(dep==0)&&d<N;i++) {ans.push_back(make_pair(u,++d));DFS(d,dep+1,maxd);}
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d %d %d",&N,&D,&K);if(N<=D||(D>1&&K<2)) {puts("NO");return 0;}for(int i=1;i<=D;i++)ans.push_back(make_pair(i,i+1));d=D+1;for(int i=2;i<=D;i++)DFS(i,0,min(i-1,D-i+1));if(d<N) {puts("NO");return 0;}puts("YES");for(int i=0;i<ans.size();i++)printf("%d %d\n",ans[i].first,ans[i].second);return 0;
}

Thanks For Reading!

如有不妥之处请在评论中指出