博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ 1196 二分答案+并查集
阅读量:7259 次
发布时间:2019-06-29

本文共 1709 字,大约阅读时间需要 5 分钟。

题目大意:n个城市,m-1条路,每条路有一级公路和二级公路之分,你要造n-1条路,一级公路至少要造k条,求出所造路的最大所需的val的最小值.

思路:首先我们一定要明确这个不是一题求所有花费的最小值的问题。然后我们只要二分答案就可以了。最后注意一下条件的拜访即可。

//看看会不会爆int!数组会不会少了一维!//取物问题一定要小心先手胜利的条件#include 
using namespace std;#define LL long long#define ALL(a) a.begin(), a.end()#define pb push_back#define mk make_pair#define fi first#define se secondconst int maxn = 10000 + 5;const int inf = 0x3f3f3f3f;struct Edge{ int u, v, val1, val2; Edge(int u = 0, int v = 0, int v1 = 0, int v2 = 0): u(u), v(v), val1(v1), val2(v2){} bool operator < (const Edge &a) const{ if (val1 != a.val1) return val1 < a.val1; return val2 < a.val2; }}e[maxn * 2];int n, k, m;int par[maxn];int pfind(int x){ if (par[x] == x) return x; return par[x] = pfind(par[x]);}bool judge(int midval){ for (int i = 1; i <= n; i++) par[i] = i; int cnt1 = 0, cnt = 0; for (int i = 1; i <= m - 1; i++){ Edge a = e[i]; int pu = pfind(a.u), pv = pfind(a.v); if (pu == pv) continue; if (a.val1 <= midval) cnt1++, cnt++, par[pu] = pv; else if (a.val2 <= midval) cnt++, par[pu] = pv; } if (cnt == n-1 && cnt1 >= k) return true; return false;}int main(){ scanf("%d%d%d", &n, &k, &m); int lb = 0, rb = 30000; for (int i = 1; i <= m - 1; i++){ int u, v, v1, v2; scanf("%d%d%d%d", &u, &v, &v1, &v2); e[i] = Edge(u, v, v1, v2); } sort(e + 1, e + m); while (lb < rb){ int mid = lb + (rb - lb) / 2; if (judge(mid)){ rb = mid; } else { lb = mid + 1; } } printf("%d\n", lb); return 0;}/*3 1 31 2 11 42 3 10 2*/
View Code

 

转载于:https://www.cnblogs.com/heimao5027/p/5857102.html

你可能感兴趣的文章
HTML 快速入门
查看>>
Linux系统密钥验证(附件有实验过程和截图)
查看>>
HDEL key field [field ...]
查看>>
dockerfile介绍与实例演示
查看>>
ceph-depoly 部署ceph 集群
查看>>
Jquery 中each循环嵌套的使用示例教程
查看>>
Windows7+VS2012下OpenGL 4的环境配置
查看>>
安全基础-A
查看>>
定义JavaScript类:工厂模式、构造函数模式、原型模式、构造函数原型模式、动态原型模式...
查看>>
zabbix修改Template OS Linux模版使已使用内存(Used memory)更准确
查看>>
OpenStack CEPH Liberty 统一存储 bug解决
查看>>
NAT总结
查看>>
Java-P:对象创建
查看>>
Oracle中的 timestamp 和 timestamp with time zone, timestamp with local time zone
查看>>
【转】MFC中listctrl控件的常用详细总结
查看>>
py django 引入 wiki 模块
查看>>
Logic-算法-分金条
查看>>
页面跳转参数不丢失
查看>>
对于 飞林沙的<把Array说透>的扩展
查看>>
使用shell脚本生成只读权限的sql脚本
查看>>