백준(BOJ) 14621 나만 안되는 연애 **

# 최소 신장 트리(MST)

기본적인 최소 신장 트리에서 남자와 여자가 이어져야 한다는 점이 추가 된 문제이다.

개념 자체는 어려운 문제는 아닌 것 같은데... 많이 안 풀어 보다 보니 코드가 지저분하다....

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#define MAX 1005
#define INF 987654321
#define MOD 1000000009
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, pi> ppi;

int n, m,a,b,c,ans=0;
int e[MAX][MAX],w[2][MAX];
char ch;
bool mw[MAX],visit[MAX];
vector<int> v[MAX];

int find()
// 현재 w[0][i] 값이 가장 작은 노드를 찾는다.
// 단, 이전 노드와 현재노드가 반대(남/여)여야 한다.
{
	int ret = -1, mi = INF;
	for (int i = 1; i <= n; i++)
	{
		if (visit[i]==false&&mw[i] != mw[w[1][i]] && mi > w[0][i])
			ret = i, mi = w[0][i];
	}
	return ret;
}

int main()
{
	fill_n(&e[0][0], MAX*MAX, INF);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf(" %c", &ch);
		mw[i] = ch == 'M' ? true : false;
		w[0][i] = INF;
	}
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		if (c < e[a][b])
		{
			v[a].push_back(b), v[b].push_back(a);
			e[a][b] = e[b][a] = c;
		}
	}
	// 데이터 입력 받기

	w[0][1] = 0, w[1][1] = 0;
	mw[0] = mw[1]?false:true;
	// 초기 설정 하기

	int cur=find();
	while (cur!=-1)
	{
		visit[cur] = true;
		for (int i = 0; i < v[cur].size(); i++)
		{
			int next = v[cur][i];
			if (visit[next]==false&&mw[cur] != mw[next] && w[0][next] > e[cur][next])
			// 이전에 방문하지 않고, 반대(남/여) 라면 노드를 갱신해 준다.
			{
				w[0][next] = e[cur][next];
				w[1][next] = cur;
			}
		}
		cur = find();
	}
	for (int i = 1; i <= n; i++)
	{
		if (w[0][i] == INF)
		{
			printf("-1");
			return 0;
		}
		// 갈 수 없는 대학이 있다면 -1 출력하고 종료한다.
		ans += w[0][i];
	}
	printf("%d", ans);
	return 0;
}