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

2019-11-06 06:32:19

字体：大中小

来源：转载

供稿：网友

题目链接:

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

题意:

题解:

其实也并不是最短路，只是用Kruskal的方法去判定符合条件的ans。我先让所有公路花费c1（保证了最大值，二分使得最大值最小），用并查集维护一下是否在一个集合，这样剩下的路就都只能用c2的钱

代码:

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define MS(a) memset(a,0,sizeof(a))#define MP make_pair#define PB push_backconst int INF = 0x3f3f3f3f;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//////////////////////////////////////////////////////////////////////////const int maxn = 2e5+10;struct node{ int x,y,c1,c2;}E[maxn];int fa[maxn];int n,k,m;int find(int x){ return fa[x]==x ? x : fa[x]=find(fa[x]);}bool check(int x){ int cnt = 0; for(int i=0; i<=n; i++) fa[i] = i; for(int i=1; i<m; i++){ if(E[i].c1 > x) continue; int p1 = find(E[i].x), p2 = find(E[i].y); if(p1 != p2){ fa[p1] = p2; cnt++; } } if(cnt < k) return false; for(int i=1; i<m; i++){ if(E[i].c2 > x) continue; int p1 = find(E[i].x), p2 = find(E[i].y); if(p1 != p2){ fa[p1] = p2; cnt++; } } if(cnt == n-1) return true; return false;}int main(){ scanf("%d%d%d",&n,&k,&m); for(int i=1; i<m; i++){ scanf("%d%d%d%d",&E[i].x,&E[i].y,&E[i].c1,&E[i].c2); } int l=0,r=3e4; int ans = 0; while(l <= r){ int mid = (l+r)/2; if(check(mid)) ans=mid,r=mid-1; else l = mid+1; } cout << ans << endl; return 0;}

上一篇：golang的基本语法

下一篇：linux ---- which

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注