위 키 오 이 - 사다리 - 1 등 향상 - 조사 집 - 1069: 범인 수감

제목 설명 Description
S 타 운 에는 현재 두 개의 교도소 가 있 으 며, 모두 N 명의 범죄자 가 수감 되 어 있 으 며, 번 호 는 각각 1 ~ N 이다.그들 사이 의 관계 도 자연히 극 에 달 했다
불협화음.많은 범죄자 들 사이 에 원한 이 쌓 여 객관 적 인 조건 이 갖 춰 지면 언제 든 충돌 이 일어 날 수 있다.원망 하 다
'기 치' (하나의 정수 치) 는 특정한 두 명의 범죄자 간 의 원한 정 도 를 나타 내 고 원한 이 클 수록 이 두 명의 범인 을 나타 낸다.
쌓 인 원한 이 많 을 수록.만약 두 명의 원한 이 c 인 범죄자 가 같은 감옥 에 갇 히 면 그들 둘 사이 에 마찰 이 생 길 것 이다.
영향력 c 의 충돌 사건 을 야기 하 다.
매년 말 경찰 서 는 올해 안에 감옥 에 있 는 모든 충돌 사건 을 영향력 에 따라 큰 것 부터 작은 것 까지 목록 을 만든다.
그리고 S 성 Z 시장 한테 보고 해.공무 가 바 쁜 Z 시장 은 리스트 에 있 는 첫 번 째 사건 의 영향력 만 본다.
만약 영향 이 매우 나쁘다 면, 그 는 경찰국장 의 경질 을 고려 할 것 이다.
N 명 범죄자 간 갈등 관 계 를 상세히 살 펴 본 경찰 국장 은 스트레스 를 크게 받 았 다.그 는 범인 들 을
두 감옥 은 충돌 사건 의 영향력 이 작 아 자신의 감 투 를 지 키 기 위해 재분배 되 었 다.가령
같은 감옥 에 있 는 두 범죄자 사이 에 원한 이 있다 면 그들 은 매년 어느 순간 마찰 을 일 으 킬 것 이다.그럼.
Z 시장 이 본 그 충돌 사건 의 영향력 을 최소 화 할 수 있 는 범인 을 어떻게 분배 해 야 할 까?이 최소 치 는 적 습 니까?
입력 설명 Input Description
첫 번 째 행 위 는 두 개의 정수 N 과 M 으로 각각 범인의 수 와 원한 이 있 는 범인의 대 수 를 나타 낸다.
다음 M 행 의 모든 행 위 는 세 개의 정수 aj, bj, cj 로 aj 호 와 bj 호 범죄자 사이 에 원한 이 존재 하고 그 원한 치 는 cj 임 을 나타 낸다.데이터 보증, 그리고 범죄자 조합 은 한 번 만 나타난다.
출력 설명 Output Description
모두 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
데이터 범위 및 알림 Data Size & Hint
범죄자 간 의 원한 치 는 아래 왼쪽 그림 에서 보 듯 이 오른쪽 그림 은 범죄자 의 분배 방법 으로 시장 이 본 충돌 사건 이다.
영향력 은 3512 (2 번 과 3 번 범죄자 로 인 한) 다.다른 어떤 분 법 도 이 분 법보 다 더 좋 을 수 없다.
【 데이터 범위 】
30% 의 데 이 터 는 N ≤ 15 입 니 다.
70% 의 데 이 터 는 N ≤ 2000, M ≤ 50000 입 니 다.
100% 의 데 이 터 는 N ≤ 20000, M ≤ 100000 입 니 다.
유형: 도 론 난이도: 2
제목: 일부 범죄자 들 은 두 범죄자 사이 의 원한 치 를 제시 합 니 다. 지금 은 이 범죄자 들 을 두 개의 감옥 으로 나 누 라 고 요구 하고 있 습 니 다. 그리고 모든 감옥 의 원한 치 는 그 중의 범죄자 들 의 가장 큰 원한 치 를 취하 고 범인 을 어떻게 분배 하 느 냐 고 물 어서 두 감옥 의 가장 큰 원한 치 를 최소 화 합 니 다.
분석: 그리고 집 제 를 조사 할 때 처음에 생각 했 던 것 이 약간 복잡 하 다. 두 범죄자 의 원한 치 를 제시 하면 두 범인 은 한 감옥 에 있 지 않 는 것 이 가장 좋다. 즉, 부 등가 의 관 계 를 제시 하기 때문에 문 제 를 푸 는 절 차 는 다음 과 같다.
1. 먼저 제 시 된 데 이 터 를 원망 치 에 따라 큰 것 에서 작은 것 으로 정렬 합 니 다.
2. 크 고 작은 데 이 터 를 옮 겨 다 니 며 opp [i] 로 범죄자 i 와 배척 하 는 범죄 자 를 대표 하여 상황 에 따라 토론 하고 현재 데 이 터 를 설정 한 범죄 자 는 a, b 이 며 원한 치 는 c 이다.
(1) 만약 a, b 가 서로 배척 하 는 범죄자 가 없다 면 opp [a] = b, opp [b] = a 를 두 고 서 로 를 서로 배척 하 는 범죄자 로 삼 는 다.
(2) 만약 에 a 가 서로 배척 하 는 b 가 없다 면 opp [a] 와 b 는 같은 감옥 에 있 고 opp [a] 와 b 를 등가 류 로 합병 하 며 opp [b] = a 를 설치한다.
(3) b 가 a 를 배척 하지 않 으 면 상황 이 유사 하 다 (2)
(4) 만약 에 a, b 가 서로 배척 하면 a, b 가 등가 류 에 있 는 지, 만약 에 있다 면 현재 의 c 는 가장 큰 원한 값 이 고 c 로 돌아 갑 니 다.같은 등가 류 가 아니라면 a 와 opp [b], b 와 opp [a] 는 같은 등가 류 에 합 쳐 opp [b] = a, opp [a] = b 를 설치한다.
(5) 다음 데 이 터 를 계속 옮 겨 다 니 기
코드:

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

int n,m,p;
int fa[20010],path[100010][3],opp[20010];

int mfind(int a)
{
    if(fa[a] != a) fa[a] = mfind(fa[a]);
    return fa[a];
}

void mmerge(int a,int b)
{
    fa[mfind(a)] = mfind(b);
}

int cmp(const void*a, const void*b)
{
    return ((int*)b)[2]-((int*)a)[2];
}

int fun(int x)
{
    if(x>=m) return 0;
    int a = path[x][0];
    int b = path[x][1];
    int c = path[x][2];
    int faa = mfind(a);
    int fab = mfind(b);
    int opa = opp[a];
    int opb = opp[b];

    int ans = 0;
    if(!opa && !opb)
    {
        opp[a] = b;
        opp[b] = a;
    }
    else if(opa && !opb)
    {
        mmerge(opa,b);
        opp[b] = a;
    }
    else if(!opa && opb)
    {
        mmerge(a,opb);
        opp[a] = b;
    }
    else
    {
        if(faa == fab)
        {
            return c;
        }
        else
        {
            mmerge(a,opb);
            mmerge(b,opa);
        }
    }
    return fun(x+1);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        fa[i] = i;
    int a,b;
    for(int i=0; i<m; i++)
    {
        for(int j=0; j<3; j++)
            scanf("%d",&path[i][j]);
    }
    qsort(path,m,sizeof(int)*3,cmp);
    
    memset(opp,0,sizeof(opp));
    printf("%d
",fun(0));
}