CCA的图

题目链接：nowcoder 213878

到主站看：https://blog.csdn.net/weixin_43346722/article/details/112135711

题目大意

有一个图，每个边都有一个值，只有值在 L~R 之间的边才能存在。
你要让两个给定的点相连，而且要让 L 最大，R 在 L 最大的情况下尽可能小。

思路

首先，因为是去值在一个区间的值，那我们把边按这个值从小到大排个序。

题目说一定要让 L 最大，那我们可以先默认 R 是在最右边。
那我们就从最后往前枚举，每次多加一条边，一旦两个点相连，就立刻停止，这个时候的 L 点就是最后的 L 点。
至于怎么看两个点是否相连，我们可以用并查集。

然后接着它说要让在这个基础上 R 值尽可能小。
那我们就从 L 点开始向后枚举，每次加边，然后也是如果相连就停止，那这个时候的区间就是我们要的区间了。
同样，我们可以用并查集来判断两点是否相连。

代码

#include<cstdio>
#include<algorithm>

using namespace std;

struct rode {
    int x, y, w;
}a[3000001];
int n, m, s, t, fa[1000001], S, T, L, R;

bool cmp(rode x, rode y) {
    return x.w < y.w;
}

int find(int now) {
    if (fa[now] == now) return now;
    return fa[now] = find(fa[now]);
}

void connect(int x, int y) {
    int X = find(x), Y = find(y);
    fa[X] = Y;
}

int main() {
    scanf("%d %d %d %d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].w);
    }

    sort(a + 1, a + m + 1, cmp);

    for (int i = 1; i <= n; i++) fa[i] = i;
    S = find(s);
    T = find(t);
    L = m + 1;
    while (S != T) {
        L--;
        connect(a[L].x, a[L].y);
        S = find(s);
        T = find(t);
    }//找到左边界的最大值

    R = L - 1;
    for (int i = 1; i <= n; i++) fa[i] = i;
    S = find(s);
    T = find(t);
    while (S != T) {
        R++;
        connect(a[R].x, a[R].y);
        S = find(s);
        T = find(t);
    }//在左边界最大的基础上，找到最小的右边界

    printf("%d %d", a[L].w, a[R].w);

    return 0;
}