VIJOS1776 – [NOIP2010]关押罪犯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68



#include <bits/stdc++.h>
#ifdef LCYTEST
#   define debug(_x) { _x }
#else
#   define debug(_x) ;
#endif
#define frie(x) ((x)<<1)
#define oppo(x) (((x)<<1)+1)
using namespace std;
const int MAX_N = 100000 + 1000;
struct tgno {
    int u, v, w;
} POOL[MAX_N]; int ppos;
typedef tgno* It;
vector<It> G;
int N, M; int Fa[MAX_N];

int find(int x) {
    if(Fa[x] == x) return x;
    return Fa[x] = find(Fa[x]);
}

void addEdge(int u, int v, int w) {
    POOL[ppos].u = u;
    POOL[ppos].v = v;
    POOL[ppos].w = w;
    G.push_back(&POOL[ppos++]);
}

int cmp(const It &a, const It &b) {
    return a->w > b->w;
}

int main() {
    cin >> N >> M;

    int u, v, w;
    for(int i=0;i<M;i++) {
        cin >> u >> v >> w;
        addEdge(u, v, w);
    }

    sort(G.begin(), G.end(), cmp);

    debug({
        for(int i=0;i<M;i++) {
            cout << G[i]->w << endl;
        }
    });

    int _ = N<<1;
    for(int i=0;i<_;i++) {
        Fa[i] = i;
    }

    for(int i=0;i<M;i++) {
        int u = G[i]->u, v = G[i]->v, w = G[i]->w;
        int fu = find(frie(u)), fv = find(frie(v));
        if(fu == fv) {
            cout << w << endl;
            return 0;
        }
        Fa[fu] = find(oppo(v));
        Fa[fv] = find(oppo(u));
    }
	
    cout << 0 << endl;
}