[낙 곡] P1525 범인 수감

낙 곡 P1525 범인 수감
제목 은 S 성에 현재 두 개의 감옥 이 있 는데 모두 N 명의 범죄자 가 갇 혀 있 고 번 호 는 각각 1 - N 이다.그들 사이 의 관계 도 자연히 극히 조 화 롭 지 못 하 다.많은 범죄자 들 사이 에 원한 이 쌓 여 객관 적 인 조건 이 갖 춰 지면 언제 든 충돌 이 일어 날 수 있다.우 리 는 '원한 치' (하나의 정수 치) 로 어떤 두 범죄자 간 의 원한 정 도 를 나타 내 고 원한 치가 클 수록 이 두 범죄자 간 의 원한 이 많아 진다.만약 에 두 명의 원한 이 c 인 범죄자 가 같은 감옥 에 갇 히 면 그들 둘 사이 에 마찰 이 발생 하고 영향력 이 c 인 충돌 사건 을 초래 할 것 이다.
매년 말 경찰 서 는 이 해 내 교도소 의 모든 충돌 사건 을 영향력 에 따라 큰 것 부터 작은 것 까지 목록 으로 만 든 뒤 S 성 Z 시장 에 게 상신 한다.공무 가 바 쁜 Z 시장 은 리스트 에 있 는 첫 사건 의 영향력 만 보 러 가 고, 영향 이 나 쁘 면 경찰국장 경질 을 검토 할 것 으로 보인다.
N 명 범죄자 간 갈등 관 계 를 상세히 살 펴 본 경찰 국장 은 스트레스 를 크게 받 았 다.그 는 충돌 사건 의 영향력 이 작 아 자신의 감 투 를 지 키 기 위해 범죄자 들 을 두 감옥 에서 재분배 할 계획 이다.같은 감옥 에 있 는 두 범죄자 사이 에 원한 이 있다 고 가정 하면 그들 은 매년 어느 순간 마찰 을 일 으 킬 것 이다.
그렇다면 어떻게 범죄 자 를 배분 해 야 Z 시장 이 본 그 충돌 사건 의 영향력 을 최소 화 할 수 있 을 까?이 최소 치 는 얼마 입 니까?
입력 형식 은 줄 마다 두 개의 숫자 사 이 를 빈 칸 으로 구분 합 니 다.첫 번 째 행 위 는 두 개의 정수 N, M 으로 범죄자 의 수 와 원한 이 있 는 범죄자 의 대 수 를 나타 낸다.다음 M 줄, 행동 마다 세 개의 정수 a j, b j, c j aj,b_j,c_j aj, bj, cj, a j aj aj 호 와 b j bj bj 호 범죄자 사이 에 원한 이 존재 하 는데 그 원한 치 는 c j c 이다.j cj​。데이터 보증 1 < a j ≤ b j ≤ N, 0 < c j ≤ 1 0 9 11 < aj ≤ bj ≤ N, 0 < cj ≤ 109, 각 범죄자 조합 은 한 번 만 나타 납 니 다.
출력 형식 은 모두 1 줄 로 Z 시장 이 본 충돌 사건 의 영향력 이다.만약 올해 내 에 감옥 에서 어떠한 충돌 사건 도 발생 하지 않 았 다 면 0 을 출력 하 십시오.
입력 \ # 1:

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

출력 \ # 1:

3512

제목 의 대 의 는 n 명 이다. 두 개의 집합 으로 나 누 어 진 다음 에 두 사람 이 함께 있 으 면 영향 수 치 를 줄 수 있다.현재 발생 하 는 영향의 최대 치 를 최소 화해 야 한다.사고방식 은 사실 딱 봐 도 알 수 있다. 가장 큰 영향 치 만 보고 욕심 을 내 서 모든 관 계 를 영향 에 따라 큰 것 에서 작은 것 으로 순 위 를 매 긴 다음 에 가장 큰 영향 치 를 가 진 두 사람 은 두 개의 집합 에 나 누 었 다. 그리고 두 번 째 큰 영향 치 는 비슷 하 게 처리 했다. 특정한 영향 치 를 발견 할 때 까지 두 사람 은 이미 한 개의 집합 에 있 었 다. 이때 어 쩔 수 없 었 다. 이 영향 치 는 바로 결과 이다.집합 은 집합 으로 이 루어 질 수 있 는데, 이런 이분 도 와 유사 한 문 제 는 어떻게 처리 해 야 합 니까?비교적 편리 한 방법 은 enemy 배열 을 사용 하 는 것 이다.범죄자 x 와 y 를 처리 할 때 x 에 enemy 가 없 으 면 추가 합 니 다.만약 x 에 enemy 가 있다 면 enemy 와 y 를 하나의 집합 에 합 쳐 감옥 에 가 두 겠 다 고 표시 합 니 다.x 와 y 를 처리 할 때마다 먼저 그들 이 한 집합 에 있 는 지 없 는 지 를 본다. 만약 에 이미 있 으 면 괜찮아, 끝났어.처음에 이 해법 을 보 았 을 때 의문 이 하나 있 었 다. x 와 y 를 처리 할 때 enemy 가 enemy 에 가입 하지 않 았 다 면 문제 가 없 었 을 것 이다. 그러나 x 에 적 z 가 있다 고 가정 하면 y 와 z 를 같은 집합 에 넣 어야 한다. 그러나 y 와 z 가 이미 적 이 었 다 면 여기 도 직접 물 러 나 지 않 았 을 것 이다. 그러면 어떻게 하지?사실 이것 은 불가능 하 다.만약 에 y 와 z 가 이미 적 이 되 었 다 면 x 는 적 z 설명 (x, z) 이 이미 처리 되 었 고 x 와 y 는 모두 z 의 적 이 며 이미 한 집합 에 있 었 다. 그러면 x 와 y 를 처리 할 때 처음에 탈퇴 한 것 을 발견 했다.코드 는 다음 과 같 습 니 다:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int n,m;
int p[20010],enemy[20010];
struct relation{
    int x,y,effect;
}relations[100010];

int findp(int i){
    if(p[i]!=i){
        p[i]=findp(p[i]);
    }
    return p[i];
}
void merge(int a,int b){
    int pa=findp(a),pb=findp(b);
    p[pa]=pb;
}
int cmp(relation a,relation b){
    return a.effect>b.effect;
}
int main(){
    memset(relations,0,sizeof(relations));
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=0;i<m;i++) cin>>relations[i].x>>relations[i].y>>relations[i].effect;
    sort(relations,relations+m,cmp);
    for(int i=0;i<m+1;i++){
        if(findp(relations[i].x)==findp(relations[i].y)){
            cout<<relations[i].effect;
            break;
        }
        if(!enemy[relations[i].x]){
            enemy[relations[i].x]=relations[i].y;
        }
        else{
            merge(relations[i].y,enemy[relations[i].x]);
        }
        if(!enemy[relations[i].y]){
            enemy[relations[i].y]=relations[i].x;
        }
        else{
            merge(relations[i].x,enemy[relations[i].y]);
        }
    }
    return 0;
}