首页 > 代码库 > BZOJ 1196 HNOI 2006 公路修建问题 二分答案+并查集
BZOJ 1196 HNOI 2006 公路修建问题 二分答案+并查集
题目大意:给出n个点,要求把它们连成一棵树,有一些边可供选择,每一条遍都有一级公路和二级公路,问在一级公路不少于k的情况下最高花费的最低值是多少。
思路:二分答案,然后验证的时候先将边按照一级公路的权值从大到小排序,我们每一次验证应该尽可能的选择能选的一级公路,如果一级公路不能选,看二级公路能不能选,如果。最后看一级公路选择的数量和总的公路选择的数量。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 20010 using namespace std; struct Edge{ int x,y; int cost,_cost; bool operator <(const Edge &a)const { return cost < a.cost; } void Read() { scanf("%d%d%d%d",&x,&y,&cost,&_cost); } }edge[MAX]; int points,k,edges; int father[MAX]; int Find(int x) { if(father[x] == x) return x; return father[x] = Find(father[x]); } inline bool Judge(int ans) { for(int i = 1; i <= points; ++i) father[i] = i; int first = 0,added = 0; for(int i = 1; i <= edges; ++i) { int fx = Find(edge[i].x); int fy = Find(edge[i].y); if(fx != fy) { if(edge[i].cost <= ans) { ++first,++added; father[fx] = fy; } else if(edge[i]._cost <= ans) { ++added; father[fx] = fy; } } } return first >= k && added == points - 1; } int main() { cin >> points >> k >> edges; for(int i = 1; i <= edges - 1; ++i) edge[i].Read(); sort(edge + 1,edge + edges + 1); int l = 0,r = 30000,ans = 30000; while(l <= r) { int mid = (l + r) >> 1; if(Judge(mid)) ans = mid,r = mid - 1; else l = mid + 1; } cout << ans << endl; return 0; }
BZOJ 1196 HNOI 2006 公路修建问题 二分答案+并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。