首页 > 代码库 > 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;}
View Code

 

hdu5102 枚举每条边的长度