[병 찰 집] 범인 수감 (BSOJ 2809)

Description
S 타 운 에는 현재 두 개의 교도소 가 있 으 며, 모두 N 명의 범죄자 가 수감 되 어 있 으 며, 번 호 는 각각 1 ~ N 이다.그들 사이 의 관계 도 자연히 극히 조 화 롭 지 못 하 다.많은 범죄자 들 사이 에 원한 이 쌓 여 객관 적 인 조건 이 갖 춰 지면 언제 든 충돌 이 일어 날 수 있다.우 리 는 '원한 치' (하나의 정수 치) 로 어떤 두 범죄자 간 의 원한 정 도 를 나타 내 고 원한 치가 클 수록 이 두 범죄자 간 의 원한 이 많아 진다.만약 에 두 명의 원한 이 c 인 범죄자 가 같은 감옥 에 갇 히 면 그들 둘 사이 에 마찰 이 발생 하고 영향력 이 c 인 충돌 사건 을 초래 할 것 이다.매년 말 경찰 서 는 이 해 내 교도소 의 모든 충돌 사건 을 영향력 에 따라 큰 것 부터 작은 것 까지 목록 으로 만 든 뒤 S 성 Z 시장 에 게 상신 한다.공무 가 바 쁜 Z 시장 은 리스트 에 있 는 첫 사건 의 영향력 만 보 러 가 고, 영향 이 나 쁘 면 경찰국장 경질 을 검토 할 것 으로 보인다.N 명 범죄자 간 갈등 관 계 를 상세히 살 펴 본 경찰 국장 은 스트레스 를 크게 받 았 다.그 는 충돌 사건 의 영향력 이 작 아 자신의 감 투 를 지 키 기 위해 범죄자 들 을 두 감옥 에서 재분배 할 계획 이다.같은 감옥 에 있 는 두 범죄자 사이 에 원한 이 있다 고 가정 하면 그들 은 매년 어느 순간 마찰 을 일 으 킬 것 이다.그렇다면 어떻게 범죄 자 를 배분 해 야 Z 시장 이 본 그 충돌 사건 의 영향력 을 최소 화 할 수 있 을 까?이 최소 치 는 얼마 입 니까?
Input
파일 이름 을 prison. in 으로 입력 하 십시오.입력 한 파일 의 줄 마다 두 개의 숫자 사 이 를 빈 칸 으로 구분 합 니 다.첫 번 째 행 위 는 두 개의 정수 N 과 M 으로 각각 범인의 수 와 원한 이 있 는 범인의 대 수 를 나타 낸다.다음 M 행 의 모든 행 위 는 세 개의 정수 aj, bj, cj 로 aj 호 와 bj 호 범죄자 사이 에 원한 이 존재 하고 그 원한 치 는 cj 임 을 나타 낸다.데이터 보증 1 ≤ aj
Output
출력 파일 prison. out 총 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
Hint
[예시 설명]
범죄자 간 의 원한 치 는 아래 왼쪽 그림 에서 보 듯 이 오른쪽 그림 은 범죄자 의 분배 방법 으로 시장 이 본 충돌 사건 의 영향력 은 3512 (2 번 과 3 번 범죄자 로 인 한 것) 이다.다른 어떤 분 법 도 이 분 법보 다 더 좋 을 수 없다.【 데이터 범 위 】 30% 의 데이터 에 대해 N ≤ 15 가 있 습 니 다.70% 의 데 이 터 는 N ≤ 2000, M ≤ 50000 입 니 다.100% 의 데 이 터 는 N ≤ 20000, M ≤ 100000 입 니 다.
Thinking
이 문 제 는 먼저 생각 하고 생각 을 모 아야 한다. 이것 은 문제 풀이 의 기초 이다.먼저 문 제 를 고려 하고, 어떻게 범인 을 안배 해야만 가장 좋 은 결정 을 내 릴 수 있 습 니까?원한 이 큰 조합 을 만들어 다른 감옥 에 넣 어야 한 다 는 것 이 분명 하 다.큰 것 부터 작은 것 까지 결정 을 내 릴 때 까지 한 팀 이 같은 감옥 에 있다 는 것 을 알 게 될 때 까지 그들의 원한 치 를 수출 하 는 것 이 최종 적 인 답 이다.이제 문제 가 또 생 겼 다. 첫 번 째 범죄 자 는 두 감옥 에 쉽게 배치 할 수 있 지만 두 번 째 조 부터 두 사람 은 어느 감옥 으로 가 야 할 까?
범인 이 어느 감옥 에 있 는 지 지 키 는 것 이 불편 하 다 면 차라리 두 범인 이 한 감옥 에 없 는 것 을 지 켜 야 한다.집합 하지 않 는 상황 을 잘 처리 하지 못 하기 때문에 우 리 는 곡선 을 그 려 나 라 를 구 해 야 한다. 특정한 점 을 보존 하 는 '적' 집합 을 통 해 그 와 한 감옥 에 없 는 범죄 자 를 대표 하고 특정한 점 이 한 곳 에 없 는 상황 을 간접 적 으로 실현 해 야 한다.관계 에 가입 할 때 판단 을 한다. 만약 에 특정한 두 점 이 하나의 집합 에 있다 면 그들 은 어떻게 해서 든 서로 다른 두 개의 감옥 을 배정 하지 못 하고 원한 치 를 수출 하면 된다 는 것 을 의미한다.
이로써 알고리즘 프레임 워 크 가 기본적으로 떠 오른다.
　　(P. s 는 두 점 을 한 집합 에 저장 하지 않 고 한 집합 에 저장 할 때 대립 점 을 사용 할 수 있 습 니 다. 즉, 모든 실제 점 에 그 와 대립 하 는 허 점 을 만 들 수 있 습 니 다. A 와 B 가 같은 집합 에 있 지 않다 는 정 보 를 읽 을 때 A 와 B, B 와 A 를 각각 연결 하면 A 와 B 가 같은 집합 에 있 지 않다 는 것 을 나 타 낼 수 있 습 니 다. 판단 과정 은 위의 방법 과 같 고 실현 도 간단 합 니 다.집에 서 한번 해 보 세 요)
Code

#include
#include
#include
using namespace std;

struct edge
{
    int x,y,v;
}cr[100050];
bool cmp(edge a,edge b) {return a.v>b.v;}
int n,m;
int an[20050],pr[20050],en[20050];

int get_father(int x)
{
    if(pr[x]==x) return x;
    pr[x]=get_father(pr[x]);
    return pr[x];
}
void Union(int x,int y)
{
    int fx=get_father(x);
    int fy=get_father(y);
    if(fx!=fy) pr[fx]=fy;
}

int main()
{
    scanf("%d%d",&n,&m);
    int x,y,v;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&cr[i].x,&cr[i].y,&cr[i].v);
    }
    sort(cr+1,cr+m+1,cmp);
    memset(pr,0,sizeof(pr));
    memset(en,0,sizeof(en));
    for(int i=1;i<=n;i++) {pr[i]=i;en[i]=0;}
    for(int i=1;i<=m;i++)
    {
        x=cr[i].x;
        y=cr[i].y;
        int fx=get_father(x);
        int fy=get_father(y);
        if(fx==fy)
        {
            printf("%d
",cr[i].v);
            return 0;
        }
        if(en[x]==0) en[x]=y;
        else Union(y,en[x]);
        if(en[y]==0) en[y]=x;
        else Union(x,en[y]);
    }
    printf("0
");
    return 0;
}