6 条题解
-
0
#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; }`
- 1
信息
- ID
- 9
- 时间
- 1000ms
- 内存
- 16MiB
- 难度
- 4
- 标签
- 递交数
- 327
- 已通过
- 148
- 上传者