二分图是一种常用的图论模型。如果一个图的顶点可以分成两个不相交子集，并且所有边关联的顶点分属于这两个不同的集合，则称这个图为二分图。

        二分图判定具有简洁的方法。

一个图是二分图的充要条件是图中没有奇数环。

        实际操作中，这个方法可以用染色法代替：

一个图是二分图当且仅当这个图可以被染成两种颜色，并且相邻两点颜色不同。

        用DFS/BFS即可进行染色分析。下面用洛谷P1525 关押罪犯来应用二分图。

题目描述

        S城现有两座监狱，一共关押着N名罪犯，编号分别为1-N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c的冲突事件。

        每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

        在详细考察了N名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

        那么，应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入输出格式

输入格式：

        每行中两个数之间用一个空格隔开。第一行为两个正整数N,M分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的M行每行为三个正整数$a_j,b_j,c_j$，表示$a_j$号和$b_j$号罪犯之间存在仇恨，其怨气值为$c_j$ 。数据保证$1<a_j≤b_j≤N ,0 < c_j≤ 1,000,000,000$，且每对罪犯组合只出现一次。对于%100的数据有$N≤ 20000,M≤ 100000$。

输出格式：

        共1行，为Z市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。

输入输出样例

Sample input

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

Sample output

3512

        很明显需要二分答案。对于一个值mid，从图中找出边权大于mid的所有边，容易知道如果此时的图是一个二分图则可以将大于mid的组合全部分开。DFS染色判断即可。

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
#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;
struct {
    int to, next, v;
} edge[200000 + 5];
int head[20000 + 5], cnt = 1, n, m, maxn = -1, vis[20000 + 5], color[20000 + 5];

inline int read() {
    char e = getchar();
    while (e < '0' || e > '9')e = getchar();
    int s = 0;
    while (e >= '0' && e <= '9')s = s * 10 + e - '0', e = getchar();
    return s;
}

inline void add(int x, int y, int z) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = z, head[x] = cnt++;
}

bool DFS(int x, int y) {
    for (int i = head[x]; ~i; i = edge[i].next) {
        if (edge[i].v > y) {
            if (color[edge[i].to] == color[x])return false;
            else if (color[edge[i].to] == 0) {
                color[edge[i].to] = -color[x];
                if (!DFS(edge[i].to, y))return false;
            }
        }
    }
    return true;
}

bool check(int x) {
    for (int i = 1; i <= n; i++)color[i] = 0;
    for (int i = 1; i <= n; i++)
        if (!color[i]) {
            color[i] = 1;
            if (!DFS(i, x))return false;
        }
    return true;
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++)head[i] = -1;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        x = read(), y = read(), z = read(), maxn = max(maxn, z);
        add(x, y, z), add(y, x, z);
    }
    int l = 0, r = maxn;
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(mid))r = mid;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}