首页 > 代码库 > HDU 5102 The K-th Distance
HDU 5102 The K-th Distance
题意：给你n-1条边，然后没两个节点的距离按照递增的顺序，求出前k项的和。
官方题解：
把所有边(u,v) 以及(v,u)放入一个队列，队列每弹出一个元素(u,v)，对于所有与u相邻的点w，如果w!=v，就把(w,u)入队。这样就能一个一个生成前K小的距离。 注意到每条边实际上会入队两次，只要把K翻倍且把ans除2即可，时间复杂度为O(n+K)；
这里只是实现一下而已。
代码：
#pragma comment(linker, "/STACK:1024000000,1024000000")#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <queue>using namespace std;#define N 100007struct node{ int u,v,d; node(int _u,int _v,int _d):u(_u),v(_v),d(_d){} node(){}};struct Edge{ int v,next;}G[2*N];int ans,k,tot,head[N];queue<node> q;void addedge(int u,int v){ G[tot].v = v; G[tot].next = head[u]; head[u] = tot++;}void bfs(){ int cnt = 0; while(!q.empty()) { node tmp = q.front(); q.pop(); int u = tmp.u, v = tmp.v, d = tmp.d; if(cnt >= k) break; for(int i=head[u];i!=-1;i=G[i].next) { int vv = G[i].v; if(vv != v) { ans += d+1; cnt++; q.push(node(vv,u,d+1)); } if(cnt >= k) break; } if(cnt >= k) break; }}int main(){ int t,n,u,v,i; scanf("%d",&t); while(t--) { while(!q.empty()) q.pop(); scanf("%d%d",&n,&k); tot = 0; memset(head,-1,sizeof(head)); for(i=1;i<=n;i++) q.push(node(i,i,0)); for(i=1;i<n;i++) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } k *= 2; ans = 0; bfs(); cout<<ans/2<<endl; } return 0;}
HDU 5102 The K-th Distance
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。