牛客练习赛74 D. CCA的图

发表于 分类于

链接

https://ac.nowcoder.com/acm/contest/9700/D

题意

无向连通图，规定只能走权值在 $[L , R]$ 内的边。

求在 $L，R$ 分别等于多少时，可以顺利从 $s$ 到达 $t$，要求 $L$ 尽可能大，在 $L$ 最大的情况下 $R$ 尽可能小。

思路

从大到小枚举边，用并查集维护点之间连通关系，当 $s$ 与 $t$ 连通时，当前边权值即为 $L$。

再枚举权值大于等于 $L$ 的边，用同样的方法确定 $R$。

代码

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
56
57
58
59
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
//head
const int N=1e6+6;
int n,m,s,t,l,r,fa[N];
struct E {
    int u,v,w;
    E() {}
    E(int u,int v,int w):u(u),v(v),w(w) {}
    bool operator < (const E &a) const {
        return w<a.w;
    }
};
vector<E> e;
int find(int x) {
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y) {
    int tx=find(x),ty=find(y);
    if(tx==ty) return;
    fa[tx]=ty;
}
int main() {
    //freopen("E:/OneDrive/IO/in.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        e.EB(u,v,w);
    }
    sort(ALL(e));
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=SZ(e)-1;i>=0;i--) {
        merge(e[i].u,e[i].v);
        if(find(s)==find(t)) {l=e[i].w;break;}
    }
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=0;i<SZ(e);i++) {
        if(e[i].w<l) continue;
        merge(e[i].u,e[i].v);
        if(find(s)==find(t)) {r=e[i].w;break;}
    }
    cout<<l<<' '<<r<<'\n';
    return 0;
}