牛客网每日刷题(3)

阅读数: 次 2021-01-07

1. CCA的图

1.1. 题目

链接：https://ac.nowcoder.com/acm/problem/213878
来源：牛客网

题目描述
是不是经常向往外面的天空呢？那就来一场说走就走的旅行吧！
你现在在 s 号城市，想去 t 号城市，城市间有双向道路，保证任意两座城市可以通过这些道路相互到达。
但是出去的人太多了，以至于政府不得不给每条道路打上标记，这个标记是一个数字，政府会规定人们只能走标记在 [L , R] 内的道路。
现在你想求出在 L，R 分别等于多少时，你可以顺利到达 t 号城市，要求 L 尽可能大，在 L 最大的情况下 R 尽可能小。

输入描述:
第一行四个正整数，n , m , s , t ，分别表示城市数量，道路数量和起点、终点城市编号。
接下来的 m 行，每行三个正整数 u , v , w ，表示有一条连接 u，v 的双向道路，其标记为 w 。

输出描述:
一行，两个正整数，表示最大的 L 和在 L 最大的情况下最小的 R 。

1.2. 样例输入&&样例输出

2 3

1	n <= 10^6 , m <= 3 × 10^6 ， s,t,u,v <= n , w <= 10^9

1.3. 思路

并查集的应用，还以为是每并一个dfs一次，没想到直接并就行了，
每一次并就检查一下是否联通，L从最大开始并,R从L之后开始并
没看清题目限制数据WA了N发，第二是没有注意到节点是从1开始的又WA了N发
第三则是输入输出的时间限制也被卡了，也WA了N发-_-真是无奈呢😔

1.4. AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 3e6+5;
#define INF 2e9
int f[maxn];
typedef long long ll;
#define sc(n) scanf("%d",&n)
struct node{
    int x,y,w;
    bool operator<(const node &x)const{
        return w<x.w;
    }
};

node a[maxn];
int find(int x){
    if(x!=f[x])
    f[x]=find(f[x]);
    return f[x];
}

void unionset(int a,int b){
    int fa=find(a);
    int fb=find(b);
    f[fa]=fb;
}

int n,m,s,t,ansl,ansr,L,R;
void init(){
    for(int i=1;i<=n;i++)f[i]=i;
}
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);
    init();
    int S=find(s),T=find(t);
    for(int i=m;i>0;i--){
        unionset(a[i].x,a[i].y);
        if(find(s)==find(t)){
            L=i;
            ansl=a[i].w;
            break;
        }
    }
    init();
    for(int i=L;i<=m;i++){
        unionset(a[i].x,a[i].y);
        if(find(s)==find(t)){
            R=i;
            ansr=a[i].w;
            break;
        }
    }
    printf("%d %d",ansl,ansr);
    system("pause");
    return 0;
}