题目描述
OI island 是一个非常漂亮的岛屿, 自开发以来, 到这儿来旅游的人很多. 然而, 由于该岛屿刚刚开发不久, 所以那里的交通情况还是很糟糕. 所以, OIER Association 组织成立了, 旨在建立 OI island 的交通系统. OI island 有 n 个旅游景点, 不妨将它们从 1 到 n 标号. 现在, OIER Association 需要修公路将这些景点连接起来. 一条公路连接两个景点. 公路有, 不妨称它们为一级公路和二级公路. 一级公路上的车速快, 但是修路的花费要大一些. OIER Association 打算修 n-1 条公路将这些景点连接起来 (使得任意两个景点之间都会有一条路径). 为了保证公路系统的效率, OIER Association 希望在这 n-1 条公路之中, 至少有 k 条(0≤k≤n-1) 一级公路. OIER Association 也不希望为一条公路花费的钱. 所以, 他们希望在满足上述条件的情况下, 花费最多的一条公路的花费尽可能的少. 而你的任务就是, 在给定一些可能修建的公路的情况下, 选择 n-1 条公路, 满足上面的条件. # 输入格式
第一行有三个数 n(1≤n≤10000),k(0≤k≤n-1),m(n-1≤m≤20000), 这些数之间用空格分开. N 和 k 如前所述, m 表示有 m 对景点之间可以修公路. 以下的 m-1 行, 每一行有 4 个正整数 a,b,c1,c2 (1≤a,b≤n,a≠b,1≤c2≤c1≤30000)表示在景点 a 与 b 之间可以修公路, 如果修一级公路, 则需要 c1 的花费, 如果修二级公路, 则需要 c2 的花费.
输出格式
一个数据, 表示花费最大的公路的花费.
主要思路:
本题主要思路是生成树 + 二分答案, 每次二分答案, check()函数的判断条件是先扫一遍 c1, 能连尽量连边, 再扫一遍 c2, 把能连的连上, 判断最后 cnt 是否等于 n-1, 即能否形成一棵生成树, 还有就是连 c1 时记录连能 c1 的数量, 判断连的 c1 边的数量 num 是否大于等于 k, 详见代码:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<cstdlib>
- #include<algorithm>
- using namespace std;
- #define maxn 20010
- #define ll long long
- #define IL inline
- #define clear(a) memset(a,0,sizeof a)
- int n,k,m,l=1e7,r=-1,ans;
- int vis[maxn],fa[maxn],take[maxn];
- struct edge{
- int x,y,valmax,valmin;
- }e[maxn];
- int findx(int x){
- if(x==fa[x])return x;
- else return fa[x]=findx(fa[x]);
- }
- int check(int x){
- clear(vis);
- for(int i=1;i<=n;i++)fa[i]=i;
- int num=0,cnt=0;
- for(int i=1;i<=m;i++){
- if(e[i].valmax<=x){
- int fx=findx(e[i].x),fy=findx(e[i].y);
- if(fx==fy)continue;
- else num++,fa[fx]=fy,cnt++;
- }
- }
- if(cnt!=n-1){
- for(int i=1;i<=m;i++){
- if(e[i].valmin<=x){
- int fx=findx(e[i].x),fy=findx(e[i].y);
- if(fx!=fy)fa[fx]=fy,cnt++;
- }
- if(cnt==n-1)break;
- }
- }
- if(cnt==n-1&&num>=k)return 1;
- else return 0;
- }
- int main(){
- scanf("%d%d%d",&n,&k,&m);
- m-=1;
- for(int i=1;i<=m;i++){
- scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].valmax,&e[i].valmin);
- r=max(r,e[i].valmax);
- l=min(l,e[i].valmin);
- }
- while(l<=r){
- int mid=(l+r)>>1;
- if(check(mid)){
- ans=mid;
- r=mid-1;
- }
- else l=mid+1;
- }
- printf("%d\n",ans);
- return 0;
- }
BZOJ1196 [HNOI2006]公路修建问题
来源: http://www.bubuko.com/infodetail-3282600.html