NOIP 2010 향상 팀 수감 자 - SilverN

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

설명 하 다.
[입 출력 사례 설명] 범죄자 간 의 원한 치 는 아래 왼쪽 그림 에서 보 듯 이 오른쪽 그림 은 범죄자 의 분배 방법 으로 시장 이 본 충돌 사건 의 영향력 은 3512 (2 번 과 3 번 범죄자 에 의 해 발생) 이다.다른 어떤 분 법 도 이 분 법보 다 더 좋 을 수 없다.
【 데이터 범 위 】 30% 의 데이터 에 대해 N ≤ 15 가 있 습 니 다.70% 의 데 이 터 는 N ≤ 2000, M ≤ 50000 입 니 다.100% 의 데 이 터 는 N ≤ 20000, M ≤ 100000 입 니 다.
 
한 무리의 죄수 들 을 두 조로 나 누 어 충돌 의 영향력 을 최소 화 하 는 것 이 목적 이다.
(왜 너희들 은 좀 잘 하지 않 고 빨리 풀 려 날 수 있 도록 하 느 냐)
갈등 이 큰 두 죄 수 를 가능 한 한 다른 감옥 으로 나 누 는 것 을 생각 하기 쉽다. 만약 헤 어 지지 못 한다 면 충돌 은 반드시 발생 할 것 이다.
어떻게 두 개의 서로 다른 감옥 을 표시 하면 코드 를 간단 하고 효율 적 으로 할 수 있 습 니까?
아버지 노드 가 같은 것 이 바로 감옥 에 있다 는 것 을 쉽게 생각 하고 수집 할 수 있다.
그러나 여전히 어려움 이 있다. 두 범인 을 갈 라 놓 으 려 면 누 구 를 어느 감옥 에 가두 어야 할 지 어떻게 알 수 있 을 까?
쉽게 (아니!) 보충 집 생각: 범죄자 a 에 대해 감옥 은 'a 가 있 는 감옥' 과 'a 가 없 는 감옥' 으로 볼 수 있다.
n 명의 범죄자 에 대해 우 리 는 찾기 범 위 를 2n 으로 확대 할 수 있다. 그 중에서 i + n 개의 노드 는 i 번 째 노드 의 '알 리 바 이' 를 나타 낸다.
 
다음은 코드:

 1 /*2010NOIP          -SilverN*/
 2 #include
 3 #include
 4 #include
 5 using namespace std;
 6 int f[200000];//        
 7 struct ed{
 8     int u,v;
 9     int c;
10 }a[500000];
11 int n,m;
12 int fd(int x){//      
13     if(f[x]==x)return x;
14     return f[x]=fd(f[x]);
15 }
16 int cmp(const ed q,const ed e){//       
17     return q.c>e.c;
18 }
19 int main(){
20     scanf("%d%d",&n,&m);
21     int i,j;
22     for(i=1;i<=m;i++){
23         scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].c);
24     }
25     for(i=1;i<=n*2;i++)f[i]=i;//       
26     sort(a+1,a+1+m,cmp);
27     int u,v,c;
28     for(i=1;i<=m;i++){
29         u=fd(a[i].u);
30         v=fd(a[i].v); 
31         if(u==v){
32             printf("%d",a[i].c);
33             return 0;
34         }
35         else{
36             f[u]=fd(a[i].v+n); 
37             f[v]=fd(a[i].u+n);
38             //           
39         }
40     }
41     printf("0");
42     return 0;
43 }

처음에는 어떤 범인 이 어느 감옥 에 넣 어야 할 지 판단 하 는 데 많은 공 을 들 였 고, 대신 의 해법 을 보고 나 서 야 보충 집 을 쓸 수 있다 는 것 을 알 게 되 었 다.
새로운 스 킬 get
다음으로 전송:https://www.cnblogs.com/AwesomeOrion/p/5418810.html