首页 > 代码库 > BZOJ 1196 HNOI2006 公路修建问题 二分答案+Kruskal
BZOJ 1196 HNOI2006 公路修建问题 二分答案+Kruskal
题目大意:给定一个无向图,一条边可以被建为一级公路或二级公路,要求一级公路的数量不小于k条,求最小生成树
最小生成树保证的是最大边最小
直接对边排序,然后二分答案,每次用Kruskal验证
先连一级边看能不能连出k条,再连剩余的边看看能不能得到最小生成树
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 10100 using namespace std; struct edge{ int x,y,f,type; bool operator < (const edge &Y) const { return f < Y.f ; } }edges[40400]; int n,k,m; int fa[M],tim[M],T; int Find(int x) { if(tim[x]!=T) fa[x]=0,tim[x]=T; if(!fa[x]||fa[x]==x) return fa[x]=x; return fa[x]=Find(fa[x]); } bool Judge(int limit) { int i,cnt=0; for(++T,i=1;i<=m&&edges[i].f<=limit;i++) if(edges[i].type==1) { int x=Find(edges[i].x); int y=Find(edges[i].y); if(x!=y) ++cnt,fa[x]=y; } if(cnt<k) return false; for(i=1;i<=m&&edges[i].f<=limit;i++) { int x=Find(edges[i].x); int y=Find(edges[i].y); if(x!=y) ++cnt,fa[x]=y; } return cnt==n-1; } int Bisection() { int l=1,r=30000; while(l+1<r) { int mid=l+r>>1; if( Judge(mid) ) r=mid; else l=mid; } if( Judge(l) ) return l; return r; } int main() { int i,x,y,a,b; cin>>n>>k>>m;m--; for(i=1;i<=m;i++) { scanf("%d%d%d%d",&x,&y,&a,&b); edges[i+i-1].x=edges[i<<1].x=x; edges[i+i-1].y=edges[i<<1].y=y; edges[i+i-1].f=a; edges[i+i-1].type=1; edges[i<<1].f=b; edges[i<<1].type=2; } m<<=1; sort(edges+1,edges+m+1); cout<<Bisection()<<endl; }
BZOJ 1196 HNOI2006 公路修建问题 二分答案+Kruskal
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。