NOIP 2010 범인 수감 (최대 생 성 트 리)

묘사 하 다.
   S 성 에는 현재 두 개의 감옥 이 있 는데, 모두 N 이 갇 혀 있다. 범인, 번 호 는 각각 1 ~ N 이다.그들 사이 의 관계 도 자연히 극히 조 화 롭 지 못 하 다.많은 범죄자 들 사이 에 원한 이 쌓 여 객관 적 인 조건 이 갖 춰 지면 언제 든 충돌 이 일어 날 수 있다.우 리 는 '원한 치' (하나의 정수 치) 로 어떤 두 범죄자 간 의 원한 정 도 를 나타 내 고 원한 치가 클 수록 이 두 범죄자 간 의 원한 이 많아 진다.하면, 만약, 만약... 의 범죄자 가 같은 감옥 에 갇 히 면 그들 둘 사이 에 마찰 이 발생 하고 영향력 이 c 이다. 라 는 충돌 사건 을 일 으 켰 다.
    매년 말 경찰 서 는 올해 내 교도소 의 모든 충돌 사건 을 영향력 에 따라 큰 것 부터 작은 것 까지 목록 을 만들어 S 에 보고 한다. 도시 시장 님 한테.공무 가 바 쁜 Z 시장 은 리스트 에 있 는 첫 번 째 사건 의 영향력 만 보 러 갈 뿐 영향 이 나 쁘 면 경찰국장 경질 을 검토 할 것 이다.
    N 을 자세히 살 펴 봤 습 니 다. 범인 간 의 갈등 관계 이후 경찰국장 은 스트레스 를 받 았 다.그 는 충돌 사건 의 영향력 이 작 아 자신의 감 투 를 지 키 기 위해 범죄자 들 을 두 감옥 에서 재분배 할 계획 이다.같은 감옥 에 있 는 두 범죄자 사이 에 원한 이 있다 고 가정 하면 그들 은 매년 어느 순간 마찰 을 일 으 킬 것 이다.그렇다면 범인 을 어떻게 분배 해 야 Z 를 시장 이 본 그 충돌 사건 의 영향력 이 가장 작 습 니까?이 최소 치 는 얼마 입 니까?
입력 형식
입력 한 파일 의 줄 마다 두 개의 숫자 사 이 를 빈 칸 으로 구분 합 니 다.
첫 번 째 행위 두 개의 정수 N M 과 각각 범인의 수 와 원한 이 있 는 범인의 대 수 를 나타 낸다.
다음 M. 행 마다 세 개의 정수 aj, bj, cj 를 표시 합 니 다. 번호 와 bj 호 범죄자 사이 에 원한 이 존재 하 는데 그 원한 치 는 cj 이다.데이터 보증 1 < = aj
출력 형식
출력 되다 시장 이 본 그 충돌 사건 의 영향력올해 안에 감옥 에서 충돌 사건 이 발생 하지 않 았 다 면 0 을 출력 하 십시오.
테스트 샘플 1
입력
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
출력
3512
비고
【 데이터 범위 】
30% 의 데이터 에 대해 N ≤ 15。
70% 의 데이터 에 대해 N ≤ 2000，M≤ 50000。
100% 데이터 에 대해 N ≤ 20000，M≤ 100000。
       제목 에 따 르 면 N 명의 범인 을 두 감옥 에 가 두 려 고 한다. 어떤 두 범인 사이 에 원한 이 하나 있 는데 두 감옥 에서 가장 큰 원한 치 를 구 하 는 동시에 이 최대 치 를 가능 한 한 작 게 해 야 한다.어떤 두 범인 이 각각 두 감옥 에 갇 혔 을 때, 그들 사이 의 원한 은 사 라 졌 다.그래서 욕심 전략 에 따라 원한 이 많은 범인 은 가능 한 한 두 감옥 에 있 도록 한다.모든 범인 을 점 으로 보고 그들 사이 의 원한 치 를 가장자리 로 보면 그림 을 만 들 고 그림 의 최대 생 성 나 무 를 구 할 수 있다.가장 큰 생 성 나무의 가장 자 리 는 반드시 결과 가 아니 라 는 것 을 쉽게 알 수 있다.그리고 최대 생 성 나무의 점 을 염색 하여 모든 점 을 2 분 의 그림 으로 구성 하여 범인 을 각각 두 개의 감옥 에 가 두 겠 다 고 밝 혔 다.그 중에서 도 염색 한 색깔 은 그들 이 있 는 감옥 을 대표 한다.마지막 으로 두 감옥 중 가장 큰 원한 치 를 구하 고 가장 큰 것 을 취하 면 된다.

#include
#include
#include
#include
#include
#include
#include
#include
#define max(a,b) ((a>b)? a:b)
using namespace std;
long n,m;
struct qianxiangxing
{long u,v,data;} w[100010];
vector s[20010];
long yanse[20010];
long chongtu[3];
long f[100010];
long gen;

bool cmp(qianxiangxing a,qianxiangxing b)
{return a.data>b.data;}

long find(long i)
{if(f[i]==i) return f[i];
 f[i]=find(f[i]);
 return f[i];}

void kelusikaer()
{long x,y;
 long t=0;
 for(long i=1;i<=m;i++) f[i]=i;
 for(long i=1;i<=m;i++){x=find(w[i].u);
                        y=find(w[i].v);
						if(x!=y){f[x]=y;
					 			 t++;
					 			 s[w[i].u].push_back(w[i].v);
					 			 s[w[i].v].push_back(w[i].u);
								 if(t==n-1) break;}}}

void ranse(long u,long se)
{if(yanse[u]!=0) return;
 yanse[u]=se;
 for(long i=0;i>n>>m;
 long a,b,c;
 for(long i=1;i<=m;i++){scanf("%d %d %d",&a,&b,&c);
						w[i].u=a;
						w[i].v=b;
						w[i].data=c;}
 sort(w+1,w+1+m,cmp);
 kelusikaer();
 ranse(1,1);/*  ，   1 2  ，1^3=2,2^3=1。 3        。*/
 for(long i=1;i<=m;i++)
 {if(yanse[w[i].u]==yanse[w[i].v]) chongtu[yanse[w[i].u]]=max(chongtu[yanse[w[i].u]],w[i].data);}/**/
 cout<


다음으로 전송:https://www.cnblogs.com/lcyzgdy/p/5877442.html