COJ 1253 2 점 + 2 - sat 판정

X 성의 정신병원 은 병실 이 두 개 밖 에 없 는데 모두 N 명의 환자 가 갇 혀 있 고 번 호 는 각각 1 ~ N 이다.환자 간 의 관 계 는 때때로 매우 조 화 롭 지 못 하 다.많은 환자 들 사이 에 원한 이 쌓 여 객관 적 인 조건 이 갖 춰 지면 언제 든 충돌 이 일어 날 수 있다.우 리 는 '불협화음 수치' (하나의 정수 치) 로 특정한 두 환자 간 의 원한 정 도 를 나타 내 고 불협화음 수치 가 클 수록 이 두 환자 간 의 원한 이 많아 진다.만약 에 두 명의 불협화음 이 c 인 환자 가 같은 병실 에 갇 히 면 그들 둘 사이 에 마찰 이 발생 하고 영향력 이 c 인 충돌 사건 을 초래 할 것 이다.매년 연말 이면 병원 에 서 는 올해 내 병실 의 모든 충돌 사건 을 영향력 에 따라 큰 것 부터 작은 것 까지 목록 을 만들어 시장 에 게 보고 한다.공무 가 바 쁜 시장 은 리스트 에 있 는 첫 번 째 사건 의 영향력 만 보고 영향 이 나 쁘 면 원장 경질 을 검토 할 것 이다.N 명 환자 간 갈등 관 계 를 상세히 살 펴 본 원장 은 오리 배가 크다 고 밝 혔 다.그 는 충돌 사건 의 영향력 이 작 아 자신의 밥그릇 을 지 키 기 위해 환자 들 을 두 병실 에서 재배 치 하려 고 한다.
같은 병실 에 있 는 두 환자 사이 에 원한 이 있다 고 가정 하면 그들 은 매년 어느 순간 마찰 이 생 길 것 이다.그렇다면 환 자 를 어떻게 분배 해 야 시장 이 본 그 충돌 사건 의 영향력 을 최소 화 할 수 있 을 까?(즉 가장 조화 로 운) 이 최소 치 는 얼마 입 니까?
Input
입력 한 파일 의 줄 마다 두 개의 숫자 사 이 를 빈 칸 으로 구분 합 니 다.
첫 번 째 행 위 는 두 개의 정수 N 과 M 으로 환자 의 수량 과 원한 이 있 는 환자 의 대 수 를 나타 낸다.
다음 M 행 각 행위 의 3 개 정수 aj, bj, cj 는 aj 호 와 bj 호 환자 사이 에 원한 이 존재 한 다 는 것 을 나타 내 며, 그 불협화음 치 는 cj 이다. 데이터 보증 1 < = aj < bj < = N, 0 < cj ≤ 1, 000, 000, 000, 000, 000, 각 환자 조합 은 한 번 만 나타난다.
Output
모두 1 행 으로 시장 이 본 그 충돌 사건 의 영향력 입 니 다. 올해 안에 정신병원 에서 충돌 사건 이 발생 하지 않 았 다 면 0 을 수출 하 십시오.
알몸 으로 문 제 를 풀 지 않다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#define MAXN 55555
#define MAXM 500005
#define INF 1000000005
using namespace std;
struct Edge
{
    int v, next;
}edge[MAXM * 2];
int n, m, e, head[MAXN];
int top, scc, index;
int x[MAXM], y[MAXM], c[MAXM];
int dfn[MAXN], low[MAXN], instack[MAXN], fa[MAXN];
int st[MAXN];
void init()
{
    top = scc = index = e = 0;
    memset(head, -1, sizeof(head));
    memset(instack, 0, sizeof(instack));
    memset(dfn, 0, sizeof(dfn));
}
void insert(int x, int y)
{
    edge[e].v = y;
    edge[e].next = head[x];
    head[x] = e++;
}
void tarjan(int u)
{
    int v;
    instack[u] = 1;
    dfn[u] = low[u] = ++index;
    st[++top] = u;
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        v = edge[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(instack[v]) low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        scc++;
        do
        {
            v = st[top--];
            instack[v] = 0;
            fa[v] = scc;
        }while(v != u);
    }
}
void build(int mid)
{
    for(int i = 1; i <= m; i++)
        if(c[i] > mid)
        {
            insert(x[i], y[i] + n);
            insert(y[i], x[i] + n);
            insert(x[i] + n, y[i]);
            insert(y[i] + n, x[i]);
        }
}
bool check()
{
    for(int i = 1; i <= 2 * n; i++)
        if(!dfn[i]) tarjan(i);
    for(int i = 1; i <= n; i++)
        if(fa[i] == fa[i + n]) return false;
    return true;
}
void solve()
{
    int low = 0, high = INF, ans = INF;
    while(low <= high)
    {
        int mid = (low + high) >> 1;
        init();
        build(mid);
        if(check()) {high = mid - 1; ans = min(ans, mid);}
        else low = mid + 1;
    }
    printf("%d
", ans);
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        for(int i = 1; i <= m; i++) scanf("%d%d%d", &x[i], &y[i], &c[i]);
        solve();
    }
    return 0;
}