HDU 4750

解题方法，，，首先应该可以看出来是一颗最小生成树，任意一条的边的价值是不同的；所以计算出最小生成树的每一条边有多少对顶点满足他的 f 值就是这条边的权值，因此可以在生成最小生成树的时候，进行一下统计，每加入一条边，就统计一下，得到 f 值和这条边权值相同有多少对顶点；方法是记录一个 rank 数组，记录每个分支里面有多少个顶点，合并的时候，以为是按照权值从小大大放入的，所以结果是 rank[a]*ran[b]*2;

#include<iostream>

#include<stdio.h>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

struct date{

    int u,v,w;

    bool operator < ( const date &a )const{

        return a.w > w;

    }

}edge[];

int N,M,Q;

int f[];__int64 rank[];

int find( int x ){

    if( x != f[x] )return f[x] = find( f[x] );

    return x;

}

int res[];  __int64 num[];

int search( int lt,int rt,int key )

{

   if( rt - lt < )

   {

        for( int i = lt; i <= rt; i++ )

        if( res[i] >= key )return i;

        return rt+;

   }

   int mid = ( lt + rt )>>;

   if( key > res[mid] )

        return search( mid,rt,key );

   else return search( lt,mid,key );

}

int main( )

{

    int u,v,w;

    while(  scanf("%d%d",&N,&M) != EOF )

    {

        for( __int64 i =; i <= M; i++ ){

            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);

        } sort( &edge[],&edge[]+M );

        for( int i =; i <= N; i++ )f[i] = i;

        for( int i =; i <= N; i++ )rank[i] =;

        int k =;

        for( int i =; i <= M; i++ )

        {

            int u = edge[i].u; int v = edge[i].v;

            int a = find( u ); int b = find( v );

            if( a != b )

            {

                res[++k] = edge[i].w;

                num[k] = rank[a]*rank[b]*;

                rank[b] += rank[a];

                f[a] = b;

            }

        }

        for( int i = k-; i >=; i-- )

            num[i] = num[i]+num[i+];

        scanf("%d",&Q);

        for( int i =; i <= Q; i++ )

        {

           int a; scanf("%d",&a);

           int pos = search(,k,a );

           if( pos > k )puts("0");

           else printf("%I64d\n",num[pos]);

        }

    }

    return;

}

巴特西

HDU 4750

最新文章

热门文章