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