首页 > 代码库 > hdu 4750 Count The Pairs 最小生成树
hdu 4750 Count The Pairs 最小生成树
题意就是给出一个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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。