P1046 [NOIP 2010 - 3] 범인 수감

시간 제한: 10000 MS   공간 제한: 65536 KB
문제 설명
S 타 운 에는 현재 두 개의 교도소 가 있 으 며, 모두 N 명의 범죄자 가 수감 되 어 있 으 며, 번 호 는 각각 1 ~ N 이다.그들 사이 의 관계 도 자연히 극히 조 화 롭 지 못 하 다.많은 범죄자 들 사이 에 원한 이 쌓 여 객관 적 인 조건 이 갖 춰 지면 언제 든 충돌 이 일어 날 수 있다.우 리 는 '원한 치' (하나의 정수 치) 로 어떤 두 범죄자 간 의 원한 정 도 를 나타 내 고 원한 치가 클 수록 이 두 범죄자 간 의 원한 이 많아 진다.만약 에 두 명의 원한 이 c 인 범죄자 가 같은 감옥 에 갇 히 면 그들 둘 사이 에 마찰 이 발생 하고 영향력 이 c 인 충돌 사건 을 초래 할 것 이다.매년 말 경찰 서 는 이 해 내 교도소 의 모든 충돌 사건 을 영향력 에 따라 큰 것 부터 작은 것 까지 목록 으로 만 든 뒤 S 성 Z 시장 에 게 상신 한다.공무 가 바 쁜 Z 시장 은 리스트 에 있 는 첫 사건 의 영향력 만 보 러 가 고, 영향 이 나 쁘 면 경찰국장 경질 을 검토 할 것 으로 보인다.N 명 범죄자 간 갈등 관 계 를 상세히 살 펴 본 경찰 국장 은 스트레스 를 크게 받 았 다.그 는 충돌 사건 의 영향력 이 작 아 자신의 감 투 를 지 키 기 위해 범죄자 들 을 두 감옥 에서 재분배 할 계획 이다.같은 감옥 에 있 는 두 범죄자 사이 에 원한 이 있다 고 가정 하면 그들 은 매년 어느 순간 마찰 을 일 으 킬 것 이다.그렇다면 어떻게 범죄 자 를 배분 해 야 Z 시장 이 본 그 충돌 사건 의 영향력 을 최소 화 할 수 있 을 까?이 최소 치 는 얼마 입 니까?
입력 형식
입력 한 파일 의 줄 마다 두 개의 숫자 사 이 를 빈 칸 으로 구분 합 니 다.첫 번 째 행 위 는 두 개의 정수 N 과 M 으로 각각 범인의 수 와 원한 이 있 는 범인의 대 수 를 나타 낸다.다음 M 행 의 모든 행 위 는 세 개의 정수 aj, bj, cj 로 aj 호 와 bj 호 범죄자 사이 에 원한 이 존재 하고 그 원한 치 는 cj 임 을 나타 낸다.데이터 보증 1 < = aj
출력 형식
Z 시장 이 본 충돌 사건 의 영향력 을 위해 총 1 줄 을 수출 한다.올해 안에 감옥 에서 충돌 사건 이 발생 하지 않 았 다 면 0 을 출력 하 십시오.
샘플 입력
4 61 4 25342 3 35121 2 283511 3 66182 4 18053 4 12884
샘플 출력
3512
제시 하 다.
【 데이터 범 위 】 30% 의 데이터 에 대해 N ≤ 15 가 있 습 니 다.70% 의 데 이 터 는 N ≤ 2000, M ≤ 50000 입 니 다.100% 의 데 이 터 는 N ≤ 20000, M ≤ 100000 입 니 다.
 
 
분석:
감옥 이 두 개 밖 에 없 으 니까 두 개 집합 이 야. 
충돌 이나 연관 관계 가 있어 서 요.
모든 죄수 에 게 대립 집합 을 만들어 라. 예 를 들 어 i 의 대립 집합 은 i 이다.
i 와 함께 갇 힐 수 없 는 죄 수 를 i 의 대립 집합 에 가두 고, 어느 순간 대립 집합 에 갇 히 면
죄수 들 이 충돌 을 일 으 켰 다 는 것 은 그 충돌 을 피 할 수 없다 는 것 을 의미한다.
 
code：
 
 

//
#include
using namespace std;
#define maxnn 50000
int f[maxnn];
int q;
int n,m;
struct node 
{
    int val,a,b;
}yu[300000];
int gf(int v)
{
    return f[v]==v? v: f[v]=gf(f[v]);
}
bool cmp(node a,node b)
{
    return a.val>b.val;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>yu[i].a>>yu[i].b>>yu[i].val;
    }
    sort(yu+1,yu+1+m,cmp);
    for(int i=1;i<=2*n;i++)
    f[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(gf(yu[i].a)!=gf(yu[i].b))
        {
            f[gf(yu[i].a)]=gf(yu[i].b+n);
            f[gf(yu[i].b)]=gf(yu[i].a+n);
        }
        else
    {
        cout<<yu[i].val;
        exit(0);
    }
    }
    cout<<0;
}