[BOJ/백준][Gold3] 13418 : 학교 탐방하기 (C++)

https://www.acmicpc.net/problem/13418

13418번: 학교 탐방하기

 

[난이도] Gold3
[유형] MST

[풀이]
피로도가 최소가 되게 할려면 edge cost가 1(내리막)인 edge를 우선으로 선택하게 해야하므로
오름차순으로 정렬, 최대가 되게 할려면 0(오르막)인 edge를 우선으로 선택하게 해야하므로
내림차순으로 정렬 뒤 Kruskal 알고리즘으로 MST를 구해주면 된다. 이 때, 총 가중치의 값은
필요 없고 선택된 edge중에 0(오르막)인 edge의 개수를 구해서 제곱해주면 최소,최대일때의
피로도를 각각 구할 수 있다.

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/13418.cpp

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N,M,uf[1001];
struct P{int a,b,c;};
vector<P> v;
int find(int a){
    if(uf[a]==a) return a;
    return uf[a]=find(uf[a]);
}
bool merge(int a,int b){
    a = find(a);
    b = find(b);
    if(a==b) return 0;
    uf[a]=b;
    return 1;
}

int ksk(){
    for(int i=0;i<=N;i++) uf[i]=i;

    int cnt=0,ret=0;
    for(int i=0;i<v.size();i++){
        if(merge(v[i].a,v[i].b)){
            if(v[i].c==0) ret++;
            if(++cnt==N) break;
        }
    }
    return ret*ret;
}

int main(){
    scanf("%d%d",&N,&M);
    M++;
    while(M--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        v.push_back({a,b,c});
    }
    sort(v.begin(),v.end(),[](P& u,P& v)->bool{
        return u.c<v.c;
    });
    int ans = ksk();

    sort(v.begin(),v.end(),[](P& u,P& v)->bool{
        return u.c>v.c;
    });
    ans -= ksk();
    printf("%d",ans);
}