[Algorithm]Baekjoon 14621번 :: 나만 안되는 연애

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
#include <mutex>
 
using namespace std;
 
 
struct Node
{
    int u, v, d;
};
 
bool cmp(const Node& a, const Node& b)
{
    return a.d < b.d;
}
 
int parents[1001] = { 0 };
bool bIsMans[1001] = { false };
 
int GetParents(int node)
{
    if (node == parents[node])
    {
        return node;
    }
 
    return parents[node] = GetParents(parents[node]);
}
 
void UnionParents(int node1, int node2)
{
    int node1Parent = GetParents(node1);
    int node2Parent = GetParents(node2);
 
    if (node1Parent < node2Parent)
    {
        parents[node2Parent] = node1Parent;
    }
    else
    {
        parents[node1Parent] = node2Parent;
    }
}
 
bool IsSameParents(int node1, int node2)
{
    return GetParents(node1) == GetParents(node2);
}
 
int n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        char c;
        cin >> c;
 
        if (c == 'M')
        {
            bIsMans[i] = true;
        }
 
        parents[i] = i;
    }
 
    vector<Node> nodes(m);
 
    for (int i = 0; i < m; ++i)
    {
        cin >> nodes[i].u >> nodes[i].v >> nodes[i].d;
    }
 
    sort(nodes.begin(), nodes.end(), cmp);
 
    int answer = 0;
 
    bool check[1001] = { false };
 
    for (int i = 0; i < m; ++i)
    {
        if (!IsSameParents(nodes[i].u, nodes[i].v) &&
            bIsMans[nodes[i].u] != bIsMans[nodes[i].v])
        {
            UnionParents(nodes[i].u, nodes[i].v);
            answer += nodes[i].d;
            check[nodes[i].u] = check[nodes[i].v] = true;
        }
    }
 
    for (int i = 1; i <= n; ++i)
    {
        if (check[i] == false)
        {
            cout << -1;
            return 0;
        }
    }
 
    cout << answer;
 
    return 0;
}
 
 
 
 
 

 

이건 설명이 살짝 모호해서 해맬수도 있는 문제긴 한데..

선택해야하는 간선은 반드시 간선의 양끝이 여대,남대여야 한다.

여대,여대거나 남대,남대면 안된다. 

그래서 MST를 만들때 부모가 같은지 체크여부말고도 서로 다른대학인지 체크해야한다.

 

거기에 더불어서, 아예 조건대로 MST가 완성이 안되는 경우의 수도 존재한다.

그렇기때문에 UnionParent를 수행할때마다 어떤 정점을 합쳤는지 따로 bool배열을 만들어서 체크해주고, 마지막에 모든 정점을 다 합쳤는지 체크후에 정답을 출력한다.