반응형
728x170
실제로 MST, 최소 신장 트리를 구현하면 된다.
나는 Prim 알고리즘을 썼다.
https://www.acmicpc.net/problem/1197
#맞는 풀이
#include <iostream>
#include <queue>
#include <functional>
#define MAX 10005
using namespace std;
using ti3 = tuple<int,int,int>;
int v,e; // 정점, 간선 개수
vector<pair<int,int>> adj[MAX]; //인접 행렬
bool check[MAX]; //MST에 쓰인지
long long Prim(){
int cnt = 0; //초기 간선 개수
long long tot = 0; //MST의 비용
priority_queue<ti3, vector<ti3>, greater<ti3>> heap;
for(auto next : adj[1]){
heap.push({next.first, 1, next.second});
}
check[1] = 1;
while(1){
int cost, v1, v2;
tie(cost, v1, v2) = heap.top();
heap.pop();
if(check[v2])continue;
check[v2] = 1;
cnt++;
tot += cost;
if(cnt == v-1) break;
for(auto next : adj[v2]){
if(check[next.second])continue;
heap.push({next.first, v1, next.second});
}
}
return tot;
}
int main(){
cin >> v >> e;
for(int i = 0; i<e; i++){
int from, to, cost;
cin >> from >> to >> cost;
adj[from].push_back({cost, to});
adj[to].push_back({cost, from});
}
long long ans = Prim();
cout << ans;
return 0;
}
Kruskal과 Union Find를 같이 알아보면 좋다.
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 11055번, 가장 큰 증가 부분 수열 : C++ [CPP] (0) | 2021.12.27 |
---|---|
백준, BOJ, 1699번, 제곱수의 합 : C++ [CPP] (0) | 2021.12.27 |
백준, BOJ, 1922번, 네트워크 연결 : C++ [CPP] ★★★★ (0) | 2021.12.23 |
백준, BOJ, 11403번, 플로이드 : C++ [CPP] ★★★★ (0) | 2021.12.23 |
백준, BOJ, 11403번, 경로 찾기 : C++ [CPP] ★★★★ (0) | 2021.12.23 |