6 条题解

  • 0
    @ 2023-4-15 15:58:02
    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    ll read(){
    	ll ans = 0 , f = 1;
    	char ch = getchar();
    	while(!isdigit(ch)){
    		f *= (ch == '-') ? -1 : 1;
    		ch = getchar();
    	}
    	while(isdigit(ch)){
    		ans = (ans << 3) + (ans << 1) + (ch ^ 48);
    		ch = getchar();
    	}
    	return ans * f;
    } 
    const int MAXN = 1e5 + 5;
    const int MAXX = 2e5 + 5; 
    struct data{
    	int x;
    	int y;
    	int z;
    };//结构体便于排序的变换
    strcut data f[MAXN];
    int n,m,a[MAXX],b[MAXX],i;
    bool cmp(data a,data b){//将结构体排序规则写入sort 
        return a.z > b.z;
    }
    int find(int x){
        if(a[x] == x) return x;
        a[x] = find(a[x]);
        return a[x];
    }
    void ad(int x,int y)//合并{
        x = find(a[x]);
        y = find(a[y]);
        a[x] = y;
    }
    bool check(int x,int y){//查找
        x = find(x);
        y = find(y);
        if(x == y) return true;
        return false;
    }
    signed main(){
        n = read() , m = read();
        for(i = 1;i <= n; i ++) 	
    		a[i] = i;
        for(i = 1;i <= m; i ++)
    		&f[i].x = read() , &f[i].y = read() , &f[i].z = read();
        sort(f + 1 , f + m + 1 , cmp);
        for(i = 1;i <= m + 1; i ++){
            if(check(f[i].x , f[i].y)){
    			printf("%d", f[i].z);
    			break;
    		}//当两个罪犯已经在同一监狱,输出答案 
            else{
                if(!b[f[i].x]) 
    				b[f[i].x] = f[i].y;//将敌人标记 
                else{
    				ad(b[f[i].x] , f[i].y);
    			}//将敌人的敌人合并
                if(!b[f[i].y])
    				b[f[i].y] = f[i].x;
                else{
    				ad(b[f[i].y] , f[i].x);
    			}
            }
        }
        return 0;
    }`
    

    信息

    ID
    9
    时间
    1000ms
    内存
    16MiB
    难度
    4
    标签
    递交数
    327
    已通过
    148
    上传者