首页 > 代码库 > [BZOJ 1196][HNOI 2006]公路修建问题
[BZOJ 1196][HNOI 2006]公路修建问题
题目链接:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1196
可以说这是个瓶颈生成树的题?
不算很难的图论题,构思非常巧妙。。。
二分生成树的最大边权x,判断这样的生成树是否存在就行了。。。
每次判断时分成两步走,首先要限制c1小于等于x,判断生成树中的树边个数是否小于等于k,若大于k,表明这个生成树不存在。
再限制c2小于等于x,由于c2<c1,所以这时候c1不用管了,能加进去的边都加进去,加完边后判断生成树的树边是不是n-1(生成树联通了所有的点),若不是,表明这个生成树不存在。
#include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> #define MAXE 20050 #define MAXV 10050 using namespace std; struct edge { int u,v,c1,c2; }edges[MAXE]; int n,m,K; int f[MAXV]; int findSet(int x) { if(f[x]==x) return x; return f[x]=findSet(f[x]); } bool judge(int x) //设生成树最大的边权为x,判断这样的生成树是否存在 { for(int i=1;i<=n;i++) f[i]=i; int cnt=0; //当前生成树中树边总数 for(int i=1;i<=m;i++) //存在生成树中c1最大值小于等于x的限制,但是办不到,这样的生成树不存在 { if(edges[i].c1>x) continue; int rootu=findSet(edges[i].u),rootv=findSet(edges[i].v); if(rootu!=rootv) { f[rootu]=rootv; cnt++; } } if(cnt<K) return false; //存在生成树中c1最大值小于等于x的限制,但是办不到,这样的生成树不存在 for(int i=1;i<=m;i++) { if(edges[i].c2>x) continue; int rootu=findSet(edges[i].u),rootv=findSet(edges[i].v); if(rootu!=rootv) { f[rootu]=rootv; cnt++; } } if(cnt<n-1) return false; //在之前的基础上加上生成树中c2最大值小于等于x的限制,但是办不到,这样的生成树不存在 return true; } int main() { scanf("%d%d%d",&n,&K,&m); for(int i=1;i<m;i++) scanf("%d%d%d%d",&edges[i].u,&edges[i].v,&edges[i].c1,&edges[i].c2); int lowerBound=1,upperBound=30000,ans; while(lowerBound<=upperBound) { int mid=(lowerBound+upperBound)/2; if(judge(mid)) { ans=mid; upperBound=mid-1; } else lowerBound=mid+1; } printf("%d\n",ans); return 0; }
[BZOJ 1196][HNOI 2006]公路修建问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。