[CodeGround] 최소 신장 트리

• 입력: 테스트케이스 T, 정점 수 N, 간선 수 M, M개의 정보 (시작점, 끝점, 가중치) 방향 없음
• 출력: 가중치의 중간값의 최소
• 알고리즘: 최소 신장 트리
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> #include <queue> #include <functional> #include <algorithm> using namespace std; vector<vector<pair<int, int> > > graph; vector<int> dis; vector<bool> visited; int main() { int testcase, n, m, u, v, w; scanf("%d", &testcase); for(int t = 1; t<=testcase; t++){ scanf("%d%d", &n, &m); graph = vector<vector<pair<int, int> > >(n + 1); visited = vector<bool>(n + 1); dis.clear(); priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q; for (int i = 0; i < m; i++) { scanf("%d%d%d", &u, &v, &w); graph[u].push_back(make_pair(v, w)); graph[v].push_back(make_pair(u, w)); } q.push(make_pair(0, 1)); int here, weight, sz, there; while (!q.empty()) { here = q.top().second; weight = q.top().first; q.pop(); if (visited[here]) continue; visited[here] = true; if(weight != 0) dis.push_back(weight); sz = graph[here].size(); for (int i = 0; i < sz; i++) { there = graph[here][i].first; if (visited[there]) continue; q.push(make_pair(graph[here][i].second, there)); } } sort(dis.begin(), dis.end()); printf("Case #%d\n%d\n", t, dis[dis.size() / 2]); } return 0; }

이 문제는 최소 스패닝트리(신장트리)에서 가중치의 합이 아닌 중간값을 저장하면 된다. 그 값을 저장해두고, 중간값을 출력하면 된다.