BOJ 13418: 학교 탐방하기

#BOJ 13418: 학교 탐방하기

13418번: 학교 탐방하기

#풀이

학교 지도를 보면 연결 그래프인 걸 알 수 있다. 또한 문제를 읽다보면 최소 신장 트리 인 것을 알 수 있다.

 

나는 문제를 잘못읽어서 입구는 무조건 간선이 1번과의 간선만 있는 줄 알고 풀었다가 틀렸다..

 

일단 이 문제는 간단하다.

 

가중치를 내림차순으로 정렬하여 최대 신장 트리를 구하고

가중치를 오름차순으로 정렬하여 최소 신장 트리를 구한 다음

 

피로도를 빼면 구할 수 있다.

 

#코드

#include<bits/stdc++.h>

using namespace std;
int n, m;
long long max_ans = 0;
long long min_ans = 0;
vector<tuple<int,int,int>> road;
vector<int> p(1001, -1);

int find(int x){
	if(p[x] < 0) return x;
	return p[x] = find(p[x]);
}
bool is_diff(int a, int b){
	int u, v;
	u = find(a); 
	v = find(b);
	if(u==v) return 0;
	if(u<=v) p[v]=u;
	else p[u]=v;
	return 1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	int a, b, w;
	
	for(int i = 0; i <=m; i++){
		cin >>a >> b>> w;
		road.push_back({w,a,b});
	}
	sort(road.begin(), road.end());
	int cnt = 0;
	for(auto nxt : road){ // 최악의 경우
		int w, a, b;
		tie(w, a, b) = nxt;
		if(!is_diff(a,b)) continue;
		
		if(w == 0) max_ans++;
		
		cnt++;
		if(cnt == n) break;
	}

	p = vector<int>(1001,-1);
	cnt=0;
	for(int i = road.size()-1; i>=0; i--){ // 최선의 경우
		int w, a, b;
		tie(w, a, b) = road[i];
		if(!is_diff(a,b)) continue;
		
		if(!w) min_ans++;
		
		cnt++;
		if(cnt == n) break;
	}
	
	cout << max_ans * max_ans - min_ans*min_ans << '\n';
	return 0;
}
//오르막기 점선 제곱, 내리막길 실선