首页 > 代码库 > hdu 4750 Count The Pairs 最小生成树

hdu 4750 Count The Pairs 最小生成树

2024-07-11 13:59:40   216人阅读

题意就是给出一个f值，然后假如两个点u，v间的所有路径上的最大边中的最小值大于f，那么这个点对是合法的，对于每个询问f，输出有多少个合法点对。

最大边最小就是最小瓶颈路，即最小生成树上的路径。一个简单的想法就是求出最小生成树后，n次dfs求出任意两点间的最大边，然后对于每个询问再查找一遍，可是时间复杂度太高。再想想的话会发现，两点间生成树上的最大边就是在克鲁斯卡尔的过程中使得他们第一次联通的那条边，所以，每加进一条边，以该边为最大边的点对就是他连接的两个集合的点对。

#include <cstdio>#include <iostream>#include <algorithm>#include <vector>using namespace std;#define maxn 500100struct edge{    int u,v,w;}e[maxn];int n,m,p[maxn],sum[maxn],tot[maxn],now;vector <int> vv;int cmp(edge a,edge b){    return a.w<b.w;}int find(int x){    if(p[x]==x) return x;    else return p[x]=find(p[x]);}void kruscal(){    int i;    now=1;    for(i=0;i<m;i++)    {        int fu=find(e[i].u);        int fv=find(e[i].v);        if(fu!=fv)        {            vv.push_back(e[i].w);            tot[now++]=sum[fu]*sum[fv]*2;            sum[fv]+=sum[fu];            p[fu]=fv;        }    }    for(i=1;i<now;i++) tot[i]+=tot[i-1];}int main(){    while(scanf("%d%d",&n,&m)!=EOF)    {        int i;        vv.clear();        for(i=0;i<500000;i++)        {            p[i]=i;            sum[i]=1;            tot[i]=0;        }        for(i=0;i<m;i++)            scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);        sort(e,e+m,cmp);        kruscal();        int cas;        scanf("%d",&cas);        int xx,temp;        for(i=1;i<=cas;i++)        {            scanf("%d",&xx);            temp=lower_bound(vv.begin(),vv.end(),xx)-vv.begin();            printf("%d\n",tot[now-1]-tot[temp]);        }    }    return 0;}
View Code

 


联系
我们