범인 을 수감 하 는 문제 풀이 [그리고 조사 집]

제목:
S 성 에는 현재 두 개의 감옥 이 있 는데 모두 N 명의 범죄자 가 갇 혀 있 고 번 호 는 각각 1 이다.  N 1~N 1 N。그들 사이 의 관계 도 자연히 극히 조 화 롭 지 못 하 다.많은 범죄자 들 사이 에 원한 이 쌓 여 객관 적 인 조건 이 갖 춰 지면 언제 든 충돌 이 일어 날 수 있다.우 리 는 '원한 치' (하나의 정수 치) 로 어떤 두 범죄자 간 의 원한 정 도 를 나타 내 고 원한 치가 클 수록 이 두 범죄자 간 의 원한 이 많아 진다.만약 에 두 명의 원한 이 c 인 범죄자 가 같은 감옥 에 갇 히 면 그들 둘 사이 에 마찰 이 발생 하고 영향력 이 c 인 충돌 사건 을 초래 할 것 이다.매년 말 경찰 서 는 이 해 내 교도소 의 모든 충돌 사건 을 영향력 에 따라 큰 것 부터 작은 것 까지 목록 으로 만 든 뒤 S 성 Z 시장 에 게 상신 한다.공무 가 바 쁜 Z 시장 은 리스트 에 있 는 첫 사건 의 영향력 만 보 러 가 고, 영향 이 나 쁘 면 경찰국장 경질 을 검토 할 것 으로 보인다.N 명 범죄자 간 갈등 관 계 를 상세히 살 펴 본 경찰 국장 은 스트레스 를 크게 받 았 다.그 는 충돌 사건 의 영향력 이 작 아 자신의 감 투 를 지 키 기 위해 범죄자 들 을 두 감옥 에서 재분배 할 계획 이다.같은 감옥 에 있 는 두 범죄자 사이 에 원한 이 있다 고 가정 하면 그들 은 매년 어느 순간 마찰 을 일 으 킬 것 이다.그렇다면 어떻게 범죄 자 를 배분 해 야 Z 시장 이 본 그 충돌 사건 의 영향력 을 최소 화 할 수 있 을 까?이 최소 치 는 얼마 입 니까?
샘플 입력:
입력 한 파일 의 줄 마다 두 개의 숫자 사 이 를 빈 칸 으로 구분 합 니 다.
첫 번 째 행 위 는 두 개의 정수 N 과 M 으로 각각 범인의 수 와 원한 이 있 는 범인의 대 수 를 나타 낸다.
다음 M 행 의 모든 행 위 는 세 개의 정수 aj, bj, cj 로 aj 호 와 bj 호 범죄자 사이 에 원한 이 존재 하고 그 원한 치 는 cj 임 을 나타 낸다.
데이터 보증 1 < = aj < = bj < = N, 0 < = cj < = 100000000, 그리고 범죄자 조합 은 한 번 만 나타 납 니 다.
샘플 출력:
출력 파일 은 모두 1 줄 로 Z 시장 이 본 충돌 사건 의 영향력 을 줍 니 다.만약 올해 내 감옥 에서 어떠한 충돌 사건 도 발생 하지 않 았 다 면, 0 을 출력 하 십시오.
문제 풀이:
먼저 c 에 대해 큰 것 부터 작은 것 까지 순 서 를 매기 고 원한 이 비교적 큰 두 사람 을 서로 다른 두 집합 에 처리한다.그 다음 에 집합 을 시작 합 니 다. 만약 에 입력 한 두 사람: a, b 가 같은 집합 에 있 으 면 그들 이 충돌 하고 c 를 출력 한 다음 에 뛰 어 내리 면 됩 니 다.만약 에 서로 다른 집합 에 있다 면 a, b 를 각각 상대방 의 적대 적 으로 집합 시 켜 야 한다. 한 마디 로 하면 두 사람 이 가능 한 한 다른 집합 에 가서 두 사람 이 충돌 하지 않도록 해 야 한다.그렇다면 어떻게 적대 집합 을 세 울 것 인가?당신 은 배열 에 n, n + i 를 추가 하여 i 의 적대 집합 을 표시 하면 됩 니 다.
코드:

#include 
#include 
#include 
using namespace std;
int fa[200005], rank[200005];
void MakeSet(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        rank[i] = 0;
    }
}
int FindSet(int x) {
    if (fa[x] != x) {
        fa[x] = FindSet(fa[x]);
    }
    return fa[x];
}
void UnionSet(int w, int e) {
    int u = w, v = FindSet(e);
    if (u == v) {
        return;
    }
    if (rank[u] > rank[v]) {
        fa[v] = u;
    } else {
        fa[u] = v;
        if (rank[u] == rank[v]) {
            rank[u]++;
        }
    }
}
struct node {
    int a, b, c;
} zui[10000005];
int cmp(node x, node y) { return x.c > y.c; }
int main() {
    int n, m, q, x, y;
    scanf("%d %d", &n, &m);
    MakeSet(n * 2);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d", &zui[i].a, &zui[i].b, &zui[i].c);
    }
    int sum = 0;
    sort(zui + 1, zui + 1 + m, cmp);
    for (int i = 1; i <= m; i++) {
    	int o = FindSet(zui[i].a), p = FindSet(zui[i].b);
        if (o == p) {//           
            printf("%d", zui[i].c);
            return 0;
        }
        UnionSet(o, zui[i].b + n);
        UnionSet(p, zui[i].a + n);//          
    }
    printf("0");
    return 0;
}