1196: [HNOI2006]公路修建问题
Time Limit: 1 Sec Memory Limit: 162 MB
题目连接
http://www.lydsy.com/JudgeOnline/problem.php?id=1196
Description
Input
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
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/二分的更多相关文章
-
BZOJ 1196 [HNOI2006]公路修建问题:二分 + 贪心生成树check(类似kruskal)
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1196 题意: n个城市,m对城市之间可以修公路. 公路有两种,一级公路和二级公路,在第i对 ...
-
BZOJ 1196 [HNOI2006]公路修建问题(二分答案+并查集)
[题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1196 [题目大意] 对于每条可能维修的公路可选择修一级公路或者二级公路,价值不同 要求 ...
-
bzoj 1196: [HNOI2006]公路修建问题 二分+并查集
题目链接 1196: [HNOI2006]公路修建问题 Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1576 Solved: 909[Submit ...
-
【最小生成树】BZOJ 1196: [HNOI2006]公路修建问题
1196: [HNOI2006]公路修建问题 Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1435 Solved: 810[Submit][Sta ...
-
BZOJ 1196: [HNOI2006]公路修建问题( MST )
水题... 容易发现花费最大最小即是求 MST 将每条边拆成一级 , 二级两条 , 然后跑 MST . 跑 MST 时 , 要先加 k 条一级road , 保证满足题意 , 然后再跑普通的 MST . ...
-
bzoj 1196: [HNOI2006]公路修建问题(二分+贪心)
传送门 解题思路 看到最大,肯定要先想二分答案.二分之后首先从小到大枚举\(k\)个小于\(lim\)的所有一级公路,然后用并查集连到一起,然后就在剩下的里面从小到大找n-1-k个二级公路,模仿最小生 ...
-
bzoj 1196: [HNOI2006]公路修建问题
Description OI island是一个非常漂亮的岛屿,自开发以来,到这儿来旅游的人很多.然而,由于该岛屿刚刚开发不久,所以那里的交通情况还是很糟糕.所以,OIER Association组织 ...
-
BZOJ_1196_[HNOI2006]公路修建问题_kruskal+二分答案
BZOJ_1196_[HNOI2006]公路修建问题_kruskal+二分答案 题意:http://www.lydsy.com/JudgeOnline/problem.php?id=1196 分析: ...
-
BZOJ1196 [HNOI2006]公路修建问题 【二分 + Kruskal】
题目 OI island是一个非常漂亮的岛屿,自开发以来,到这儿来旅游的人很多.然而,由于该岛屿刚刚开发不久,所以那里的交通情况还是很糟糕.所以,OIER Association组织成立了,旨在建立O ...
随机推荐
-
python3.5------三级菜单
笔者QQ :360212316 逻辑图 代码 city = { "华南": { "广东": ["广州市", "佛山市", ...
-
elk深度解析
上面的两张图是elk的一个架构 下面是对logstash分析:如下图 可以看出 logstash的一个角色shipper,(是通过配置文件来决定logstash是shipper还是indexer)注意 ...
-
在Windows下部署安装hexo
由于hexo的文档里并没有一步步详细写出过程的细节,在Windows下又更麻烦,所以就很容易入坑. 安装 安装github for windows,msysgit 安装包: https://githu ...
-
Asp.net Vnext api CORS( 跨域)
概述 跨域资源共享(CORS )是一种网络浏览器的技术规范,它为Web服务器定义了一种方式,允许网页从不同的域访问其资源.而这种访问是被同源策略所禁止的.CORS系统定义了一种浏览器和服务器交互的方式 ...
-
解析 this.initialize.apply(this, arguments)
一. 起因 那天用到prototype.js于是打开看看,才看几行就满头雾水,原因是对js的面向对象不是很熟悉,于是百度+google了一把,最后终于算小有收获,写此纪念一下^_^. prototyp ...
-
POJ1470 Closest Common Ancestors
LCA问题,用了离线的tarjan算法.输入输出参考了博客http://www.cnblogs.com/rainydays/archive/2011/06/20/2085503.htmltarjan算 ...
-
SDP协议分析
一.SDP协议介绍 SDP 完全是一种会话描述格式 ― 它不属于传输协议 ― 它只使用不同的适当的传输协议,包括会话通知协议(SAP).会话初始协议(SIP).实时流协议(RTSP).MIME 扩展协 ...
-
Nodejs 集成到IIS
http://www.hanselman.com/blog/WebMatrixAndNodejsTheEasiestWayToGetStartedWithNodeOnWindows.aspx http ...
-
使用 OpenSSL 创建私有 CA:2 中间证书
OpenSSL 创建私有 CA 三部曲:使用 OpenSSL 创建私有 CA:1 根证书使用 OpenSSL 创建私有 CA:2 中间证书使用 OpenSSL 创建私有 CA:3 用户证书 本文将在前 ...
-
SAP从入门到精通 知识体系
初步认识 SAP标准课程培训 详细信息点击: SAP从入门到精通课程 标准培训主要是基于SAP标准的课程架构,定期在SAP的培训中心面向广大SAP客户开设公开课.培训过程中会应用SAP标准的教材内容, ...