关押罪犯

洛谷-P1525-关押罪犯

分析

见《进阶指南》第424页。

实现

#include <iostream>
#include <cstring>
using namespace std;

const int N = 20010, M = 100010;
struct edge {
    int to, next, w;
};
edge e[2 * M];
int idx, head[N];
int n, m;
bool flag, mark[2 * M];
int c[N];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void dfs (int cur, int color) {
    c[cur] = color;
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to;
        if (mark[i] == false) continue;
        if (c[to] == color) {
            flag = false;
            return;
        }
        if (c[to] == 0) dfs(to, 3 - color);
    }
}
bool check (int x) {
    memset(mark, 0, sizeof(mark));
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; ++ i)
        for (int j = head[i]; j != -1; j = e[j].next)
            if (e[j].w > x)
                mark[j] = true;
    flag = true;
    for (int i = 1; i <= n; ++ i) {
        if (c[i] == 0) {
            dfs(i, 1);
            if (flag == false) return false;
        }
    }
    return true;
}

int main () {
    memset(head, -1, sizeof(head));
    int l = 0, r = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, w; i <= m; ++ i) {
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
        r = max(r, w);
    }

    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid) == true)
            r = mid;
        else
            l = mid + 1;
    }
    printf("%d", l);
    return 0;
}