題意：給你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; } View Code

?

轉載于:https://www.cnblogs.com/whatbeg/p/4087765.html

總結

以上是生活随笔為你收集整理的HDU 5102 The K-th Distance的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。