CodeForces 404C Restore Graph

本文主要是介绍CodeForces 404C Restore Graph，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

n个点的图  最大度为k  已知从某个点到每个点的距离dis[i]  求  这幅图的边

思路：

告诉了距离  很容易想到dis是从距离为0的那个点开始bfs求出来的

那么复原这幅图的办法就是重新构造这棵bfs形成的树就好了

每层利用点数计算一下是不是违反了最大度k的限制

这里注意  只有dis=0的那个点可以连出k条边  其余的只有k-1条（因为它们还和父亲连着一条边）

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define M 100010int n,m,yes;
struct node
{int id,dis;bool operator<(const node ff) const{return dis<ff.dis;}
}nd[M];
int fa[M],qu[M],d[M];
int lasl,lasr,now,root;int main()
{int i,j,k;scanf("%d%d",&n,&m);for(i=1;i<=n;i++){scanf("%d",&d[i]);nd[i].id=i;nd[i].dis=d[i];}sort(nd+1,nd+n+1);for(i=1;i<=n;i++){if(!nd[i].dis) qu[lasr++]=nd[i].id;}if(lasr==1){yes=1;now=1;i=2;root=qu[0];while(i<=n){while(i<=n&&nd[i].dis==d[qu[lasl]]+1){qu[now++]=nd[i].id;i++;}if( (now==lasr) || (root==qu[lasl]&&now-lasr>(__int64)(lasr-lasl)*m)|| (root!=qu[lasl]&&now-lasr>(__int64)(lasr-lasl)*(m-1)) ){yes=0;break;}for(j=lasr,k=0;j<now&&lasl<lasr;j++){fa[qu[j]]=qu[lasl];k++;if( (root==qu[lasl]&&k==m) || (root!=qu[lasl]&&k==m-1) ){k=0;lasl++;}}lasl=lasr;lasr=now;}}if(!yes) printf("-1\n");else{printf("%d\n",n-1);for(i=1;i<=n;i++){if(fa[i]) printf("%d %d\n",i,fa[i]);}}return 0;
}

这篇关于CodeForces 404C Restore Graph的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---