首页 > 代码库 > 【分块答案】【最小生成树】【kruscal】bzoj1196 [HNOI2006]公路修建问题
【分块答案】【最小生成树】【kruscal】bzoj1196 [HNOI2006]公路修建问题
二分(分块)枚举 边权上限。用kruscal判可行性。
#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;int u[20001],v[20001],w1[20001],w2[20001],n,m,K,Limit;int fa[10001],rank[10002];void init(){ for(int i=1;i<=n;i++) fa[i]=i; memset(rank,0,(n+1)*sizeof(int));}int findroot(int x){ if(x==fa[x]) return x; int rt=findroot(fa[x]); fa[x]=rt; return rt;}void Union(const int &U,const int &V){ if(rank[U]<rank[V]) fa[U]=V; else { fa[V]=U; if(rank[U]==rank[V]) ++rank[U]; }}bool Kruscal(int x)//仅仅需要接通即可。 { init(); int cnt=0; for(int i=1;i<=m;++i) if(w1[i]<=x) { int f1=findroot(u[i]),f2=findroot(v[i]); if(f1!=f2) { Union(f1,f2); ++cnt; if(cnt==n-1) return 1; } } if(cnt<K) return 0; for(int i=1;i<=m;++i) if(w2[i]<=x) { int f1=findroot(u[i]),f2=findroot(v[i]); if(f1!=f2) { Union(f1,f2); ++cnt; if(cnt==n-1) return 1; } } return cnt==n-1?1:0;}int main(){ scanf("%d%d%d",&n,&K,&m); for(int i=1;i<=m;++i) { scanf("%d%d%d%d",&u[i],&v[i],&w1[i],&w2[i]); Limit=max(Limit,w1[i]); } int sz=sqrt(Limit),last=0; for(int i=1;last<=Limit;i+=sz) { if(Kruscal(i)) for(int j=last+1;j<=i;++j) if(Kruscal(j)) { printf("%d\n",j); return 0; } last=i; }}
【分块答案】【最小生成树】【kruscal】bzoj1196 [HNOI2006]公路修建问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。