728x90
https://www.acmicpc.net/problem/1647
최소신장트리(MST)를 만드는 알고리즘을 약간 응용한 문제이다.
우선 주어진 입력을 바탕으로 MST를 생성한다.(프림 또는 크루스칼 이용)
문제에서 요구하는 조건을 만족하기 위해서는, 생성된 최소신장트리에서 간선의 비용이 가장 큰 것을 하나 찾은 뒤 그곳을 기점으로 잘라주면(=간선을 제거하면) 문제의 조건을 충족시킬 수 있다.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define P pair<int, int>
int visited[100001];
vector<P> edge[100001];
//우선순위 큐(minheap)를 이용하여 방문할 수 있는 정점중 가중치가 가장 낮은 정점으로 이동
ll prim() {
ll ans = 0; int cut =0;
priority_queue<P, vector<P> , greater<P>>pq; // first는 가중치 second 는 정점
pq.push(P(0, 1)); //1번 정점부터 시작
// 가중치가 가장작은것이 top으로 가게된다!
while(!pq.empty()) {
P cur = pq.top();
pq.pop();
if(visited[cur.second]) //방문 정점 표시
continue;
visited[cur.second] = 1;
// 비용이 최대인 간선 찾기
cut = max(cur.first,cut);
ans += cur.first;
for (int i = 0; i < edge[cur.second].size(); i++) { //현재 정점에서 이동 할 수 있는 방문하지 않은 정점 푸쉬
if (!visited[edge[cur.second][i].second]) {
pq.push(edge[cur.second][i]);
}
}
}
return ans-cut;
}
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int V, E;
cin >> V >> E;
for(int i = 0; i < E; i++) {
int A,B,C;
cin >> A >> B >> C;
edge[A].push_back(P(C, B));
edge[B].push_back(P(C, A));
}
ll result = prim();
cout<< result;
return 0;
}
728x90
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
[백준/파이썬] 13904번 과제 (0) | 2023.01.10 |
---|---|
[백준/파이썬] 2225번 합분해 (0) | 2023.01.09 |
[백준/C++] 2473번 세 용액 (1) | 2023.01.05 |
[백준/파이썬] 2166번 다각형의 면적 (0) | 2023.01.03 |
[백준/파이썬] 9466번 텀 프로젝트 (1) | 2023.01.03 |