ch4901 带权并查集

#include <cstdio> #include <iostream> #include <iomanip> #include <string> #include <cstdlib> #include <cstring> #include <queue> #include <set> #include <vector> #include <map> #include <algorithm> #include <cmath> #include <stack> #define INF 0x3f3f3f3f #define IMAX 2147483646 #define LINF 0x3f3f3f3f3f3f3f3f #define ll long long #define ull unsigned long long #define uint unsigned int using namespace std; int fa[21111], d[21111]; int get(int x) { if (fa[x] == x)return x; int ff = get(fa[x]); d[x] ^= d[fa[x]]; return fa[x] = ff; } void merge(int x, int y) { int fx = get(x), fy = get(y); fa[fx] = fy; d[fx] = d[x] ^ d[y] ^ 1; } struct Node { int a, b, val; bool operator<(const Node &c) const { return val > c.val; } }a[211111]; int n, m; int main() { scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].val); sort(a, a + m); for (int i = 0; i < n; i++) fa[i] = i, d[i] = 0; for (int i = 0; i < m; i++) { int fx = get(a[i].a), fy = get(a[i].b); if (fx == fy) { if (d[a[i].a] ^ d[a[i].b] == 0) { printf("%d\n", a[i].val); return 0; } } else merge(a[i].a, a[i].b); } printf("0\n"); return 0; }