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; }