풀백준 1647

https://www.acmicpc.net/problem/1647

문제를 해결하다

이 문제를 잘 분석해보면 큰 문제이고, 마을을 둘로 나누는 문제다. mst로 쉬운데 마을이 둘로 갈라지네요..? 조금만 생각해보면 가장 작은 Edge를 가진 Village들을 mst로 먼저 연결하고 그 중에서 가중치가 가장 큰 Edge를 빼면 쉽게 Village를 둘로 나눌 수 있음을 알 수 있습니다.

우리는 Prim 알고리즘을 사용했습니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <limits.h>
#include <utility>
#include <vector>
#include <queue>

using namespace std;

struct cmp
{
	bool operator()(const pair<int, int>& a, const pair<int, int>& b)
	{
		return a.second > b.second;
	}
};

vector<pair<int, int> > node(100001);
int visit(100001);
priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> pq;



int main()
{
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	int N, M;
	

	cin >> N >> M;
	for (int i = 0; i < M; ++i)
	{
		int A, B, C;
		cin >> A >> B >> C;
		node(A).push_back({ B, C });
		node(B).push_back({ A, C });
	}

	int max_wei = 0;
	int sum = 0;
	int cnt = 0;
	
	pq.push({ 1, 0 });
	while (!pq.empty())
	{
		pair<int, int> cur = pq.top();
		pq.pop();

		if (visit(cur.first))
			continue;
		max_wei = max(max_wei, cur.second);
		sum += cur.second;
		visit(cur.first) = 1;
		++cnt;
		if (cnt == N)
			break;
		for (int i = 0; i < node(cur.first).size(); ++i)
			pq.push(node(cur.first)(i));
		
	}
	cout << sum - max_wei;
	return 0;
}

메모리: 56604KB, 시간: 792ms