16562 친구비
알고리즘 (union find)
1
2
1. unionfind 를 구현하되, 루트에 친구비가 적은 것이 오도록함
2. 루트만 골라 친구비를 정산한다.
코드
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
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAX_STUDENT 10001
using namespace std;
int numOfStudent, numOfFriendship, money, students[MAX_STUDENT], minMoney, studentGroup[MAX_STUDENT];
void unionStudent(int first, int second);
int find(int element);
bool makeFriend();
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> numOfStudent >> numOfFriendship >> money;
for (int i = 1; i <= numOfStudent; i++) {
cin >> students[i];
studentGroup[i] = i;
}
for (int i = 0; i < numOfFriendship; i++) {
int first, second;
cin >> first >> second;
unionStudent(first, second);
}
if (makeFriend())
cout << minMoney;
else
cout << "Oh no";
}
//값이 작은 게 루트에 오도록
void unionStudent(int first, int second) {
first = find(first);
second = find(second);
if (students[first] <= students[second])
studentGroup[second] = first;
else
studentGroup[first] = second;
}
int find(int element) {
if (studentGroup[element] == element)
return element;
else
return find(studentGroup[element]);
}
bool makeFriend() {
for (int i = 1; i <= numOfStudent; i++) {
if (studentGroup[i] == i) {
if (money < students[i])
return false;
minMoney += students[i];
money -= students[i];
}
}
return true;
}