首页 > 代码库 > hdu 5102 The K-th Distance

hdu 5102 The K-th Distance

2024-08-01 06:34:40   212人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=5102

补题.

题意：给你n-1条边，然后没两个节点的距离按照递增的顺序，求出前k项的和。

思路：把所有边(u,v) 以及(v,u)放入一个队列，队列每弹出一个元素(u,v)，对于所有与u相邻的点w，如果w!=v，就把(w,u)入队。这样就能一个一个生成前K小的距离。 注意到每条边实际上会入队两次，只要把K翻倍且把ans除2即可，时间复杂度为O(n+K)；

 1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 #include <vector> 5 #include <algorithm> 6 using namespace std; 7  8 int t,n,k; 9 struct node10 {11     int u,v,w;12     node(int u,int v,int w):u(u),v(v),w(w){}13 };14 15 int main()16 {17     scanf("%d",&t);18     while(t--)19     {20         queue<node>q;21         vector<int>g[100001];22         scanf("%d%d",&n,&k);23         k*=2;24         for(int i=1; i<=n-1; i++)25         {26             int u,v;27             scanf("%d%d",&u,&v);28             g[u].push_back(v);29             g[v].push_back(u);30         }31         for(int i=1; i<=n; i++)32         {33             q.push(node(i,i,0));34         }35         int cnt=0; long long ans=0;36         while(cnt<k)37         {38             node e=q.front(); q.pop();39             int u=e.u;40             for(int j=0; j<(int)g[u].size(); j++)41             {42                 int v=g[u][j];43                 if(v!=e.v&&cnt<k)44                 {45                     q.push(node(v,u,e.w+1));46                     cnt++;47                     ans+=e.w+1;48                 }49             }50         }51         printf("%lld\n",ans/2);52     }53     return 0;54 }
View Code

 

hdu 5102 The K-th Distance


联系
我们