코드

#include <iostream>
using namespace std;
#include <vector>
#include <queue>
#include <algorithm>
int check[100001];
typedef struct _node
{
    /* data */
    int next;
    long long cost;
} Node;
vector<Node> graph[100001];
vector<long long> vec;
struct cmp
{
    bool operator()(Node e1, Node e2)
    {
        if (e1.cost > e2.cost)
            return true;
        else
            return false;
    }
};
priority_queue<Node, vector<Node>, cmp> pq;
long long sum = 0;
int last = -1;
void prim()
{
    while (!pq.empty())
    {
        Node temp = pq.top();
        int tempnext = temp.next;
        long long tempcost = temp.cost;
        pq.pop();
        if (check[tempnext])
            continue;
        check[tempnext] = 1;
        vec.push_back(tempcost);
        // sum += tempcost;
        // last = tempcost;
        auto list = graph[tempnext];
        for (int i = 0; i < list.size(); i++)
        {
            int next = list[i].next;
            long long cost = list[i].cost;
            pq.push({next, cost});
        }
    }
}
int main(void)
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    check[1] = 1;
    auto temp = graph[1];
    for (int i = 0; i < temp.size(); i++)
    {
        int next = temp[i].next;
        long long cost = temp[i].cost;
        pq.push({next, cost});
    }
    prim();
    sort(vec.begin(), vec.end());
    long long sum = 0;
    for (int i = 0; i < vec.size() - 1; i++)
    {
        sum += vec[i];
        // cout << vec[i] << " ";
    }
    cout << sum;
    return 0;
}

문제 접근

1. 최소 스패닝 트리 - 프림 알고리즘

• 임의의 정점하나를 선택. 연결된 모든 간선 우선순위 큐에 넣어줌.
• 가장 작은 cost 갖는 노드 선택하고
• 그 노드와 관련된 모든 간선 다시 우선순위큐에 넣어줌.
• 모든 노드가 선택될 때 까지 반복.

해결 방법

최소 스패닝 트리 - 프림 알고리즘을 이용한다.
최소스패닝트리를 구하면, 그 중 가장 큰 최대 간선을 빼준다.