首页 > 代码库 > codeforces C. Restore Graph

codeforces C. Restore Graph

2024-11-27 09:44:39   203人阅读

题意：构造一个有n个顶点，每个点度不超过k，然后给出每一个点到达一个定点的最短距离d数组，然后构造出这样的一个图；

思路：排序之后，有两个距离为0的或者没有直接输出-1，然后用两个游动下表，后面的与前面的度都小于k且它们的距离相差1，就建1条边。然后dfs输出就可以。

技术分享
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <cmath> 6 #include <vector> 7 #define maxn 100010 8 using namespace std; 9 10 int n,k;11 int d[maxn];12 int du[maxn];13 struct node14 {15     int x,id;16     bool operator <(const node &a)const17     {18         return x<a.x;19     }20 } p[maxn];21 vector<int>g[maxn];22 23 void dfs(int x)24 {25     for(int i=0; i<(int)g[x].size(); i++)26     {27         printf("%d %d\n",x,g[x][i]);28         dfs(g[x][i]);29     }30 }31 32 int main()33 {34     scanf("%d%d",&n,&k);35     for(int i=1; i<=n; i++)36     {37         scanf("%d",&d[i]);38         p[i].x=d[i];39         p[i].id=i;40     }41     sort(p+1,p+n+1);42     if(p[1].x==0&&p[2].x==0||p[1].x!=0)43     {44         printf("-1\n");45         return 0;46     }47     int l=1,r=2;48     int cnt=0;49     bool flag=false;50     while(r<=n)51     {52         if(p[r].x==p[l].x)53         {54             printf("-1\n");55             return 0;56         }57         if(p[r].x-p[l].x==1&&du[p[l].id]<k&&du[p[r].id]<k)58         {59             g[p[l].id].push_back(p[r].id);60             cnt++;61             du[p[l].id]++;62             du[p[r].id]++;63             r++;64         }65         else if(p[r].x-p[l].x>1||du[p[l].id]>=k)66         {67             l++;68             if(l==r)69             {70                 flag=true;71                 break;72             }73         }74         else if(du[p[r].id]>=k)75         {76             r++;77         }78         else79         {80             r++;81         }82     }83     if(flag)84     {85         printf("-1\n");86         return 0;87     }88     printf("%d\n",cnt);89     dfs(p[1].id);90     return 0;91 }
View Code

 

codeforces C. Restore Graph


联系
我们