对于这题我们可以运用贪心的策略，将怒气值从大到小排序，从大到小一直让两人分离，如果找到一对无法分离(即在同一个监狱里)的就输出他们的怒气值，否则输出 0 0 0。 并查集维护一个 p r e [ i ] pre[i] pre[i]数组，下标 1 1 1到 n n n维护的是 1 − n 1-n 1−n所在的监狱，下标 n + 1 n+1 n+1到 2 n 2n 2n维护的是 1 − n 1-n 1−n所在监狱的另一个监狱。例如分离 a 、 b a、b a、b，则合并 a a a和 b + n b+n b+n以及 b b b和 a + n a+n a+n。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 20000 + 5; const int maxm = 100000 + 5; int n, m, pre[maxn << 1]; struct node{ int u, v, w; }e[maxm]; int find(int x){ return x == pre[x] ? pre[x] : pre[x] = find(pre[x]); } void join(int x, int y){ int rt1 = find(x), rt2 = find(y); if(rt1 != rt2){ pre[rt1] = rt2; } } int main(){ cin >> n >> m; for(int i = 1; i <= (n << 1); i++) pre[i] = i;//开两倍, a + n表示a所在的另一个监狱, b + n表示b所在的另一个监狱 for(int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w; sort(e + 1, e + 1 + m, [&](const node &a, const node &b){return a.w > b.w;}); for(int i = 1; i <= m; i++){ if(find(e[i].u) == find(e[i].v)){ cout << e[i].w << '\n'; return 0; } join(e[i].u, e[i].v + n); join(e[i].v, e[i].u + n); } cout << 0 << '\n'; return 0; }