首页 > 代码库 > hdu5102 枚举每条边的长度
hdu5102 枚举每条边的长度
题意 给了 一颗 有 100000 个节点的树, 他们构成的边有 n*(n-1)/2 种。 每条边有一个长度,长度排序后 取前K条的 和, 枚举每条长度为1 的边 放进队列,然后通过成都为1 的表去 形成长度为2的边,然后不断地接下去, 枚举到 K个就可以了 K <1000000
#include <iostream>#include <algorithm>#include <string.h>#include <cstdio>#include <queue>#include <vector>using namespace std;const int maxn=1000005;typedef long long ll;struct point{ int L,R; int Rper; ll len; point(int a=0,int c=0, int d=0,ll e=0){ L=a; R=c; Rper=d; len=e; }};vector<int> F[100005];queue<point> Q;int main(){ int cas=0; scanf("%d",&cas); for(int cc=1; cc<=cas; ++cc){ int n,k; scanf("%d%d",&n,&k); for(int i=0; i<=n; ++i) F[i].clear(); while(!Q.empty())Q.pop(); int rea=0,frt=0; point t1,t2; for(int i=1; i<n; ++i){ int a,b; scanf("%d%d",&a,&b); F[a].push_back(b); F[b].push_back(a); Q.push(point(a,b,a,1)); rea++; Q.push(point(b,a,b,1)); rea++; } ll ans=0; for(frt=0; frt<2*k; ++frt){ t1= Q.front(); Q.pop(); ans=ans+t1.len; if(rea>=2*k) {continue;} int sz = F[t1.R].size(); for(int i=0; i<sz; ++i){ int to = F[t1.R ][i]; if(to!=t1.Rper&&rea<2*k){ t2.L=t1.L; t2.len=t1.len+1; t2.R=to; t2.Rper=t1.R; rea++; Q.push(t2); } } } printf("%I64d\n",ans/2); } return 0;}
hdu5102 枚举每条边的长度
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。