AcWing 1142 바 쁜 도시

제목 설명:
도시 C 는 매우 바 쁜 대도시 로 도시 안의 도로 가 매우 붐벼 서 시장 은 그 중의 도 로 를 개조 하기 로 결정 했다.
도시 C 의 도 로 는 이렇게 분포 한다.
도시 n 교차로 1 ∼ n 은 어떤 교차로 사이 에 도로 가 연결 되 어 있 고, 두 교차로 사이 에는 최대 한 개의 도로 가 연결 되 어 있다.
이 길 들 은 쌍방 향 모든 교차 로 를 직간 접적 으로 연결 했다.
모든 도로 에 하나의 가치 가 있 는데 가치 가 작 을 수록 이 도로 가 바 쁠 수록 개조 가 필요 하 다 는 것 을 나타 낸다.
그러나 시 정부의 자금 이 제한 되 어 시장 이 개 조 를 원 하 는 길 은 적 을 수록 좋다. 그래서 그 는 다음 과 같은 요 구 를 했다.
1. 개 조 된 그 도 로 는 모든 교차 로 를 직간 접적 으로 연결 할 수 있다.
2. 요구 1 을 만족 시 키 는 상황 에서 개 조 된 도 로 는 되도록 적다.
3. 요구 1, 2 를 만족 시 키 는 상황 에서 개 조 된 도로 의 최대 치 는 최대한 작다.
시 기획 국 의 당신 으로서 가장 좋 은 결정 을 내 려 야 합 니 다. 그 도 로 를 선택 하면 건설 되 어야 합 니 다.
입력 형식
첫 줄 에는 두 개의 정수 가 있다. n,m 있다 n 교차로 하나의 길.
다음 m 줄 은 모든 도로 에 대한 설명 입 니 다. 줄 마다 세 개의 정수 u, v, c 를 포함 합 니 다. 교차로 u 화해시키다 v 도로 연결 c。
출력 형식
두 정수 s, max 는 몇 개의 도 로 를 선 택 했 는 지, 점수 가 가장 큰 도로 의 점수 가 얼마 인지 나타 낸다.
데이터 범위
1≤n≤300, 1≤m≤8000, 1≤c≤10000
입력 예시:

4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8

출력 예시:

3 6

분석:
이 문 제 는 그림 의 최소 생 성 트 리 중 변 권 이 가장 큰 변 이 가장 작은 지, 본질은 kruskal 알고리즘 에 대한 이 해 를 고찰 하 는 것 이다.
최소 생 성 트 리 를 만 들 려 면 n - 1 개의 변 을 선택해 야 합 니 다. 생 성 트 리 에서 변 권 이 가장 큰 변 을 최소 화하 기 위해 서 는 변 권 이 가장 작은 n - 1 개의 변 을 선택해 야 합 니 다. 그러나 이 n - 1 개의 변 이 반드시 생 성 트 리 를 구성 할 수 있 는 것 은 아니 므 로 큰 것 부터 작은 것 까지 연결 되 지 않 는 변 을 삭제 한 다음 에 n 번 째 큰 변 부터 생 성 트 리 에 추가 하려 고 합 니 다.완전한 생 성 트 리 를 구성 할 때 이때 사용 하 는 최대 변 권 이 가장 적 습 니 다. 이 과정 은 kruskal 알고리즘 의 과정 과 같 기 때문에 kruskal 알고리즘 이 구 한 최소 생 성 트 리 는 나무의 가중치 와 최소 일 뿐만 아니 라 최대 변 권 도 가장 작 습 니 다.지난 문제 의 코드 에 조금 만 수정 하면 본 문 제 를 해결 할 수 있다.

#include 
#include 
#include 
using namespace std;
const int N = 305,M = 8005;
int n,m,fa[N];
struct edge{
    int a,b,w;
    bool operator < (const edge &ed)const{
        return w < ed.w;
    }
}e[M];
int find(int x){
    if(fa[x] != x)  fa[x] = find(fa[x]);
    return fa[x];
}
int main(){
    cin>>n>>m;
    int a,b,c;
    for(int i = 1;i <= n;i++)   fa[i] = i;
    for(int i = 0;i < m;i++){
        cin>>a>>b>>c;
        e[i] = {a,b,c};
    }
    sort(e,e + m);
    int res = 0;
    for(int i = 0;i < m;i++){
        a = find(e[i].a),b = find(e[i].b),c = e[i].w;
        if(a != b)  fa[a] = b,res = c;
    }
    cout<