题解 CF746G 【New Roads】
pzc2004
2020-05-24 19:52:33
# 题目分析
显然，一个城市是死胡同等价于它是叶子结点。
我们先考虑这个图上最少会有几个叶子结点。显然每一层的城市只能往上一层的城市连边，所以我们可以发现如果这一层的城市数比上一层的城市数多了 $x$ 个，那么这张图的叶子结点的个数就增加了 $x$ 个，否则不变。也就是这张图上最少会有 $\sum_{i=1}^{t}\max(a_i-a_{i-1},0)$ 个叶子结点，令这个数等于 $ma$。
所以如果 $k$ 小于最小的叶子结点数，那么就可以直接输出-1了。接下来考虑怎么构造。
显然我们只需要让构造出的图多出 $k-ma$ 个叶子结点即可。我们就只需要在每一层往上一层连边的时候分类讨论一下，如果 $a_i$ 大于 $a_{i-1}$，就只往上一层中 $a_{i-1}-\min(a_{i-1}-1,k)$ 个城市连边，然后把 $k$ 减去 $\min(a_{i-1}-1,k)$；如果 $a_i$ 小于 $a_{i-1}$，就只往上一层中 $a_i-\min(a_i-1,k)$ 个城市连边，然后把 $k$ 减去 $\min(a_i-1,k)$。最后如果 $k$ 刚好等于0就说明可以，否则就输出-1。
``` cpp
#include<bits/stdc++.h>
using namespace std;
#define N 200001
int n,t,k,a[N],ma,las,cnt,tot;
struct sb
{
int a,b;
}ans[N];
signed main()
{
scanf("%d%d%d",&n,&t,&k);
las=0,cnt=1;
for(register int i=1;i<=t;i++)
{
scanf("%d",&a[i]);
ma+=max(0,a[i]-a[i-1]);//计算最少的叶子结点数
las=cnt,cnt+=a[i];
}
if(ma>k){printf("-1");return 0;}//不行的情况
k-=ma;
las=0,cnt=1;
for(register int i=1;i<=t;i++)
{
for(register int j=1;j<=a[i];j++)
{
ans[++tot].a=cnt+j;//这条边的一个端点为该点
if(a[i]>=cnt-las)//往上一层连边
{
ans[tot].b=las+(j-1)%(cnt-las-min(cnt-las-1,k))+1;
}else
{
ans[tot].b=las+(j-1)%(a[i]-min(a[i]-1,k))+1;
}
}
if(a[i]>=cnt-las)
{
k-=min(cnt-las-1,k);
}else
{
k-=min(a[i]-1,k);
}
las=cnt,cnt+=a[i];
}
if(k==0)
{
printf("%d\n",n);
for(register int i=1;i<=tot;i++)printf("%d %d\n",ans[i].a,ans[i].b);
}else printf("-1");
return 0;
}
```