문제 URL : www.acmicpc.net/problem/16562
16562번: 친구비
첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (
www.acmicpc.net
문제 접근법 :
단순한 분리집합 문제입니다.
늘 묶어야하는 비용들은 늘최소로 묶어주기만하면 끝나는 문제이기에 어려운 문제가아닙니다.
소스코드 :
|
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
|
//By 콩순이냉장고
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int parent[10001];
int cost[10001];
int n, m, k;
int find(int idx)
{
if (idx == parent[idx])
return idx;
return parent[idx] = find(parent[idx]);
}
void Union(int idx1, int idx2){
idx1 = find(idx1);
idx2 = find(idx2);
if (idx1 == idx2)
return;
cost[idx2] = min(cost[idx1], cost[idx2]);
cost[idx1] = cost[idx2];
parent[idx2] = idx1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
int visit[10001] = { 0 };
for (int i = 1; i <= n; i++)
{
parent[i] = i;
cin >> cost[i];
}
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
Union(x, y);
}
for (int i = 1; i <= n; i++)
{
visit[find(i)] = 1;
}
int sum = 0;
for (int i = 1; i <= n; i++)
{
if (visit[i]){
if (k - cost[i] < 0)
{
cout << "Oh no\n";
return 0;
}
k -= cost[i];
sum += cost[i];
}
}
cout << sum << "\n";
}
|
cs |
모르는점 혹은 궁금한점 혹은 논리적인 오류가 있다면 언제든지 댓글을 이용해주시길 바랍니다.
'백준' 카테고리의 다른 글
| 백준 16953 A → B (2) | 2020.12.27 |
|---|---|
| 백준 1107 리모컨 (0) | 2020.11.29 |
| 백준 10216 Count Circle Groups (0) | 2020.10.02 |
| 백준 5373 큐빙(SW 역량 테스트 기출 문제) (0) | 2020.09.21 |
| 백준 4195 친구 네트워크 (0) | 2020.08.30 |
