codeground practice - 최소 신장 트리

문제 링크

---

로그인을 해야만 볼 수 있다.

문제 해결

---

 1. 신장 트리를 만들되, 선택된 간선들의 중간 값이 가장 최소가 되는 신장 트리를 만들어야한다. 말이 복잡하지만 결국은 MST를 구하는 문제다. 왜냐면 간선들의 중간 값은 가중치가 작은 간선들이 많을 수록 작아지기 때문이다.

주의할 점 || 생각해볼 점

---

 -

참고

---

 - 

	/*
	explanation in vjerksen.tistory.com
	*/
	#include <iostream>
	#include <cstdio>
	#include <cstdlib>
	#include <cstring>
	#include <algorithm>
	#include <vector>
	#include<queue>
	using namespace std;
	int T,N,M;
	int parent[1004];
	int r[1004];
	int _find(int x){
	if(x==parent[x])
	return x;
	else
	return parent[x]=_find(parent[x]);
	}
	void _union(int u,int v){
	u=_find(u),v=_find(v);
	if(r[u]>r[v]){
	parent[v]=u;
	}
	else{
	parent[u]=v;
	}
	if(r[u]==r[v])
	r[u]++;
	}
	int main(){
	cin >> T;
	for(int z=1;z<=T;z++){
	vector<pair<int,pair<int,int> > > graph;
	vector<int> ans;
	scanf("%d %d",&N,&M);
	for(int i=0;i<M;i++){
	int u,v,w;
	scanf("%d %d %d",&u,&v,&w);
	graph.push_back({w,{u,v}});
	}
	memset(r,0,sizeof(r));
	for(int i=1;i<=N;i++){
	parent[i]=i;
	}
	sort(graph.begin(),graph.end());
	ans.push_back(0);
	for(int i=0;i<M;i++){
	int u,v,w;
	w=graph[i].first;
	u=graph[i].second.first;
	v=graph[i].second.second;
	if(_find(u)!=_find(v)){
	_union(u,v);
	ans.push_back(w);
	}
	}
	printf("Case #%d\n%d\n",z,ans[(N)/2]);
	}
	return 0;
	}

view raw codeground(최소신장트리).cpp hosted with ❤ by GitHub

※ 정확하고 부드러운 태클은 언제나 환영입니다.