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

题目链接:

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

题意:

题解:

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

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 2e5+10;
17 
18 struct node{
19     int x,y,c1,c2;
20 }E[maxn];
21 
22 int fa[maxn];
23 int n,k,m;
24 
25 int find(int x){
26     return fa[x]==x ? x : fa[x]=find(fa[x]);
27 }
28 
29 bool check(int x){
30     int cnt = 0;
31     for(int i=0; i<=n; i++)
32         fa[i] = i;
33     for(int i=1; i<m; i++){
34         if(E[i].c1 > x) continue;
35         int p1 = find(E[i].x), p2 = find(E[i].y);
36         if(p1 != p2){
37             fa[p1] = p2;
38             cnt++;
39         }
40     }
41     if(cnt < k) return false;
42     for(int i=1; i<m; i++){
43         if(E[i].c2 > x) continue;
44         int p1 = find(E[i].x), p2 = find(E[i].y);
45         if(p1 != p2){
46             fa[p1] = p2;
47             cnt++;
48         }
49     }
50     if(cnt == n-1) return true;
51     return false;
52 }
53 
54 int main(){
55 
56     scanf("%d%d%d",&n,&k,&m);
57     for(int i=1; i<m; i++){
58         scanf("%d%d%d%d",&E[i].x,&E[i].y,&E[i].c1,&E[i].c2);
59     }
60 
61     int l=0,r=3e4;
62     int ans = 0;
63     while(l <= r){
64         int mid = (l+r)/2;
65         if(check(mid)) ans=mid,r=mid-1;
66         else l = mid+1;
67     }
68 
69     cout << ans << endl;
70 
71     return 0;
72 }