BZOJ 1196: [HNOI2006]公路修建问题 Kruskal/二分

时间:2022-12-30 22:35:58

1196: [HNOI2006]公路修建问题

Time Limit: 1 Sec  Memory Limit: 162 MB

题目连接

http://www.lydsy.com/JudgeOnline/problem.php?id=1196

Description

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条公路,满足上面的条件。

Input

第一行有三个数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的花费。1≤n,m≤100000,0≤ai≤100000,1≤xi≤n,0≤wi≤10000,1≤li≤ri≤n

Output

一个数据,表示花费最大的公路的花费。

Sample Input

10 4 20
3 9 6 3
1 3 4 1
5 3 10 2
8 9 8 7
6 8 8 3
7 1 3 2
4 9 9 5
10 8 9 1
2 6 9 1
6 7 9 8
2 6 2 1
3 8 9 5
3 2 9 6
1 6 10 3
5 6 3 1
2 7 6 1
7 8 6 2
10 9 2 1
7 1 10 2

Sample Output

5

HINT

题解:

二分L,然后用kruskal来进行check,首先判断会不会超过K,搞一搞就出来了!

代码:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 20001
#define mod 10007
#define eps 1e-9
//const int inf=0x7fffffff; //无限大
const int inf=0x3f3f3f3f;
/* */
//************************************************************************************** inline ll read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct node{
int x,y,c1,c2;
}e[maxn];
int fa[maxn];
int n,k,m;
int fin(int x)
{
return x==fa[x]?x:fa[x]=fin(fa[x]);
}
int jud(int x)
{
for(int i=;i<=n;i++)
fa[i]=i;
int cnt=;
for(int i=;i<m;i++)
{
if(e[i].c1>x)continue;
int p=fin(e[i].x),q=fin(e[i].y);
if(fin(p)!=fin(q))
{
fa[q]=p;
cnt++;
}
}
if(cnt<k)return ;
for(int i=;i<m;i++)
{
if(e[i].c2>x)continue;
int p=fin(e[i].x),q=fin(e[i].y);
if(fin(p)!=fin(q))
{
fa[q]=p;
cnt++;
}
}
if(cnt==n-)return ;
return ;
}
int main()
{
n=read(),k=read(),m=read();
for(int i=;i<=m-;i++)
{
e[i].x=read(),e[i].y=read(),e[i].c1=read(),e[i].c2=read();
}
int l=,r=,mid=(l+r)/;
int ans=mid;
while(l<=r)
{
mid=(l+r)/;
if(jud(mid)){r=mid-,ans=mid;}
else l=mid+;
}
printf("%d\n",ans);
}

BZOJ 1196: [HNOI2006]公路修建问题 Kruskal/二分的更多相关文章

  1. BZOJ 1196 &lbrack;HNOI2006&rsqb;公路修建问题:二分 &plus; 贪心生成树check(类似kruskal)

    题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1196 题意: n个城市,m对城市之间可以修公路. 公路有两种,一级公路和二级公路,在第i对 ...

  2. BZOJ 1196 &lbrack;HNOI2006&rsqb;公路修建问题(二分答案&plus;并查集)

    [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1196 [题目大意] 对于每条可能维修的公路可选择修一级公路或者二级公路,价值不同 要求 ...

  3. bzoj 1196&colon; &lbrack;HNOI2006&rsqb;公路修建问题 二分&plus;并查集

    题目链接 1196: [HNOI2006]公路修建问题 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 1576  Solved: 909[Submit ...

  4. 【最小生成树】BZOJ 1196&colon; &lbrack;HNOI2006&rsqb;公路修建问题

    1196: [HNOI2006]公路修建问题 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 1435  Solved: 810[Submit][Sta ...

  5. BZOJ 1196&colon; &lbrack;HNOI2006&rsqb;公路修建问题&lpar; MST &rpar;

    水题... 容易发现花费最大最小即是求 MST 将每条边拆成一级 , 二级两条 , 然后跑 MST . 跑 MST 时 , 要先加 k 条一级road , 保证满足题意 , 然后再跑普通的 MST . ...

  6. bzoj 1196&colon; &lbrack;HNOI2006&rsqb;公路修建问题&lpar;二分&plus;贪心&rpar;

    传送门 解题思路 看到最大,肯定要先想二分答案.二分之后首先从小到大枚举\(k\)个小于\(lim\)的所有一级公路,然后用并查集连到一起,然后就在剩下的里面从小到大找n-1-k个二级公路,模仿最小生 ...

  7. bzoj 1196&colon; &lbrack;HNOI2006&rsqb;公路修建问题

    Description OI island是一个非常漂亮的岛屿,自开发以来,到这儿来旅游的人很多.然而,由于该岛屿刚刚开发不久,所以那里的交通情况还是很糟糕.所以,OIER Association组织 ...

  8. BZOJ&lowbar;1196&lowbar;&lbrack;HNOI2006&rsqb;公路修建问题&lowbar;kruskal&plus;二分答案

    BZOJ_1196_[HNOI2006]公路修建问题_kruskal+二分答案 题意:http://www.lydsy.com/JudgeOnline/problem.php?id=1196 分析: ...

  9. BZOJ1196 &lbrack;HNOI2006&rsqb;公路修建问题 【二分 &plus; Kruskal】

    题目 OI island是一个非常漂亮的岛屿,自开发以来,到这儿来旅游的人很多.然而,由于该岛屿刚刚开发不久,所以那里的交通情况还是很糟糕.所以,OIER Association组织成立了,旨在建立O ...

随机推荐

  1. python3&period;5------三级菜单

    笔者QQ :360212316 逻辑图 代码 city = { "华南": { "广东": ["广州市", "佛山市", ...

  2. elk深度解析

    上面的两张图是elk的一个架构 下面是对logstash分析:如下图 可以看出 logstash的一个角色shipper,(是通过配置文件来决定logstash是shipper还是indexer)注意 ...

  3. 在Windows下部署安装hexo

    由于hexo的文档里并没有一步步详细写出过程的细节,在Windows下又更麻烦,所以就很容易入坑. 安装 安装github for windows,msysgit 安装包: https://githu ...

  4. Asp&period;net Vnext api CORS&lpar; 跨域&rpar;

    概述 跨域资源共享(CORS )是一种网络浏览器的技术规范,它为Web服务器定义了一种方式,允许网页从不同的域访问其资源.而这种访问是被同源策略所禁止的.CORS系统定义了一种浏览器和服务器交互的方式 ...

  5. 解析 this&period;initialize&period;apply&lpar;this&comma; arguments&rpar;

    一. 起因 那天用到prototype.js于是打开看看,才看几行就满头雾水,原因是对js的面向对象不是很熟悉,于是百度+google了一把,最后终于算小有收获,写此纪念一下^_^. prototyp ...

  6. POJ1470 Closest Common Ancestors

    LCA问题,用了离线的tarjan算法.输入输出参考了博客http://www.cnblogs.com/rainydays/archive/2011/06/20/2085503.htmltarjan算 ...

  7. SDP协议分析

    一.SDP协议介绍 SDP 完全是一种会话描述格式 ― 它不属于传输协议 ― 它只使用不同的适当的传输协议,包括会话通知协议(SAP).会话初始协议(SIP).实时流协议(RTSP).MIME 扩展协 ...

  8. Nodejs 集成到IIS

    http://www.hanselman.com/blog/WebMatrixAndNodejsTheEasiestWayToGetStartedWithNodeOnWindows.aspx http ...

  9. 使用 OpenSSL 创建私有 CA:2 中间证书

    OpenSSL 创建私有 CA 三部曲:使用 OpenSSL 创建私有 CA:1 根证书使用 OpenSSL 创建私有 CA:2 中间证书使用 OpenSSL 创建私有 CA:3 用户证书 本文将在前 ...

  10. SAP从入门到精通 知识体系

    初步认识 SAP标准课程培训 详细信息点击: SAP从入门到精通课程 标准培训主要是基于SAP标准的课程架构,定期在SAP的培训中心面向广大SAP客户开设公开课.培训过程中会应用SAP标准的教材内容, ...