首页 > 代码库 > hdu 5102 The K-th Distance （队列+生成法，，）
hdu 5102 The K-th Distance （队列+生成法，，）
题意：
N个点的一棵树。定义点u和点v的距离等于它们之间的路径（唯一的）的长度。这样我们可以得到n*(n-1)/2个距离。
将它们从小到大排序，问前K个数的和是多少。
思路：
将边长为1的树枝都入队列。每次取出一个，然后从这根树枝的前端生出一个新点，变成距离加1的一根新树枝，将其入队列。如此操作下去。
可得到所有的各种长度的树枝。因为每根树枝其实有两个在队列里（互为方向生长），故求前2*K个数的和，然后除以2。
*：我们取前队列里的前2K个，就算后面的若干些不是一对一对的，也一定可以取2K个以后的一些数与这2K个数的一些交换，将2K个数调整为一对一对的形式。（画个样例想想就明白了）
例子：
1-2-3 树枝： (1->2),(2->1),(2->3),(3->2),(1->2->3),(3->2->1)
代码：（*：生成够2K个数就可以及时退出了，不然TLE）
struct node{ int u,v,len;}edge[2000100];vector<int> graph[100100];int T,n,k;int main(){ cin>>T; while(T--){ scanf("%d%d",&n,&k); int c=0; rep(i,1,n) graph[i].clear(); rep(i,1,n-1){ int x,y; scanf("%d%d",&x,&y); graph[x].push_back(y); graph[y].push_back(x); edge[++c].u=x, edge[c].v=y, edge[c].len=1; edge[++c].v=x, edge[c].u=y, edge[c].len=1; } int p=0; while(p<=c){ if(c>=2*k) break; ++p; int U=edge[p].u, V=edge[p].v; int L=graph[U].size(); rep(i,0,L-1) if(graph[U][i]!=V && c<2*k){ ++c; edge[c].u=graph[U][i]; edge[c].v=U; edge[c].len=edge[p].len+1; } } ll ans=0; int ts=min(c,2*k); rep(i,1,ts) ans+=(ll)edge[i].len; printf("%I64d\n",ans/2); }}
hdu 5102 The K-th Distance （队列+生成法，，）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。