16562 ์น๊ตฌ๋น
์๊ณ ๋ฆฌ์ฆ (union find)
1. unionfind ๋ฅผ ๊ตฌํํ๋, ๋ฃจํธ์ ์น๊ตฌ๋น๊ฐ ์ ์ ๊ฒ์ด ์ค๋๋กํจ
2. ๋ฃจํธ๋ง ๊ณจ๋ผ ์น๊ตฌ๋น๋ฅผ ์ ์ฐํ๋ค.
์ฝ๋
#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;
}