洛谷1396 营救

发表于 | 分类于 |
字数统计: 389 字

题目地址

题解

为什么专门拿出这道题来写一个题解呢？
因为这道题考察到了一个我们平时（可能）
没有注意到的地方。
并查集不仅可以用来做连通性状态的维护，还可以用来解决一些图论上的最值问题。
像是这道题，就把二分和并查集结合在一起。
二分答案，只把拥挤度小于答案的加入并查集，维护$S$和$T$的联通状态。
这个思路真的很妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
typedef long long ll;
struct Edge{
    int u,v,cost; 
}; 
Edge edge[20005];
bool cmp(int a,int b){
    return edge[a].cost<edge[b].cost;
}
int id[20005],n,m,S,T;
int par[10005];
int Find(int x){
    if(par[x]==x)return x;
    return par[x]=(Find(par[x]));
}
void Unite(int u,int v){
    par[Find(u)]=Find(v);
}
bool judge(int M){
    for(int i=1;i<=n;i++)
        par[i]=i;
    for(int i=0;i<m;i++){
        if(edge[id[i]].cost>M)break;
        Unite(edge[id[i]].u,edge[id[i]].v); 
        if(Find(S)==Find(T))return 1;
    }
    return 0;
}
void init(){
    scanf("%d%d%d%d",&n,&m,&S,&T);
    for(int i=0;i<m;i++)
        scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].cost),
        id[i]=i;
    sort(id,id+m,cmp);
}
void solve(){
    int L=0,R=20000,M;
    while(R-L){
        M=(R+L)/2;
        if(judge(M))//<=M
            R=M;
        else L=M+1;
    }
    printf("%d\n",L);
}
int main(){
    init();
    solve();
    return 0;
}