[BAE/<JOON> 문제풀이] 14621. 나만 안되는 연애

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

14621번: 나만 안되는 연애

핵심::
MST 기본 문제

풀이::
처음보고 프림 알고리즘 + 이분 그래프 개념으로 풀어야하나 싶었다.

하지만 간단하게 생각해보면 그냥 양 끝단의 성별이 같은 간선 자체를 제외하면 크루스칼 알고리즘으로 해결 할 수 있다.

의견::
프림 알고리즘 한번도 구현 안해봐서 풀기 싫었는데 프림 아니었음

프림으로도 구현 자체는 될 거 같다. 

 

코드::

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct e {
	int start, dest, dist;
};

int parent[1001];
int findp(int x) {
	if (parent[x] == x) return x;
	return parent[x] = findp(parent[x]);
}

bool cmp(e a, e b) {
	return a.dist < b.dist;
}

int main()
{
	int n, m; cin >> n >> m;
	bool gen[1001];
	for (int i = 1; i <= n; i++) {
		char v;
		cin >> v;
		gen[i] = (v == 'M');
		parent[i] = i;
	}

	vector<e> arr;

	for (int i = 1; i <= m; i++) {
		int s, e, l;
		cin >> s >> e >> l;
		if (gen[s] == gen[e]) continue;
		arr.push_back({ s, e, l });
	}

	m = arr.size();

	sort(arr.begin(), arr.end(), cmp);

	int esum = 0;
	int dsum = 0;

	for (int i = 0; i < m; i++) {
		int p1 = findp(arr[i].start);
		int p2 = findp(arr[i].dest);
		if (p1 != p2) {
			parent[p2] = p1;
			dsum += arr[i].dist;
			if (++esum == n - 1) {
				cout << dsum;
				return 0;
			}
		}
	}

	cout << -1;

	return 0;
}