-
Notifications
You must be signed in to change notification settings - Fork 2
/
14621_josueyeon.cpp
93 lines (73 loc) · 1.67 KB
/
14621_josueyeon.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// MST: kruskal algorithm
// 이때 대학교의 그룹이 같은 경우는 간선 vector에 추가하지 않는다
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int parent[1001];
bool IsWoman[1001];
int findParent(int x)
{
return (x == parent[x] ? x : parent[x] = findParent(parent[x]));
}
void unionParent(int a, int b)
{
a = findParent(a);
b = findParent(b);
if (a < b)
parent[b] = a;
else
parent[a] = b;
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
// N(node), M(edge)
int N, M;
cin>>N>>M;
for(int i = 1; i <= N;i++)
{
char univ;
cin>>univ;
if (univ == 'W')
IsWoman[i] = true;
else if (univ == 'M')
IsWoman[i] = false;
}
for(int i = 1;i <= N;i++)
parent[i] = i;
vector<pair<int, pair<int, int>>> graph;
for(int i = 0;i < M;i++)
{
int a, b, c;
cin>>a>>b>>c;
if (IsWoman[a] != IsWoman[b])
graph.push_back({c, {a, b}});
}
sort(graph.begin(), graph.end());
long result = 0;
for(int i = 0;i < graph.size();i++)
{
int a = graph[i].second.first;
int b = graph[i].second.second;
int w = graph[i].first;
if (findParent(a) != findParent(b))
{
unionParent(a, b);
result += w;
}
}
for(int i = 1;i <= N;i++)
{
if (findParent(i) != findParent(1))
{
result = -1;
break;
}
}
cout<<result<<"\n";
return 0;
}