[C++] 백준 14621번: 나만 안되는 연애

문제 링크

14621번: 나만 안되는 연애

문제 요약

여초 대학교와 남초 대학교 사이의 간선만 이용해서 모든 정점을 연결하는 부분 그래프를 만들어야 한다. 이때 필요한 간선들의 가중치 합의 최솟값을 구해야 한다.

접근 방법

MST 기본 문제에서 두 가지가 더 추가되었습니다. 먼저 여초 대학교와 남초 대학교 사이의 간선만 사용해야 하고, MST를 만들 수 없는 경우에는 -1을 출력해야 합니다.

첫번째 제약사항의 경우 문제의 맨 처음에 각 학교의 성별 정보가 주어지는 것을 이용하면 됩니다. 뒤에서 간선에 대한 입력이 주어질 때, 두 정점의 성별을 비교해서 다른 경우에만 간선을 정의해주면 됩니다.

두번째로 MST를 만들 수 없는 경우입니다. 제 경우에는 크루스칼 알고리즘을 이용해서 구현을 했는데, MST를 구한 뒤에 1번 정점과 다른 모든 정점을 비교해서 같은 set에 있는지 확인하는 방식을 통해서 MST가 만들어졌는지, 만들 수 없는지 판단할 수 있습니다.

기본적인 MST 문제와 난이도 차이는 거의 없다고 보면 될거 같습니다.

이번 문제에서는 괄호를 평소와 다르게 써봤는데 그리 익숙하지는 않지만 코드가 위아래로 짧아진거 같아서 괜찮은거 같습니다.

코드

#include <bits/stdc++.h>

using namespace std;

struct Edge {
	int u, v, d;

	bool operator<(const Edge& a) {
		return d < a.d;
	}
};

const int MAX = 1001;
int parent[MAX];
char univ[MAX];
vector<Edge> edges;

int Find(int a) {
	if (a == parent[a])
		return a;
	return parent[a] = Find(parent[a]);
}

void Union(int a, int b) {
	int pa = Find(a), pb = Find(b);
	parent[pa] = pb;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		cin >> univ[i];
		parent[i] = i;
	}

	for (int i = 0; i < m; i++) {
		int u, v, d;
		cin >> u >> v >> d;

		if (univ[u] != univ[v])
			edges.push_back({ u, v, d });
	}

	sort(edges.begin(), edges.end());

	int ans = 0;
	for (auto& i : edges) {
		if (Find(i.u) != Find(i.v)) {
			Union(i.u, i.v);
			ans += i.d;
		}
	}

	bool flag = false;
	for (int i = 2; i <= n; i++)
		if (Find(1) != Find(i))
			flag = true;

	cout << (flag ? -1 : ans);
	return 0;
}