반응형

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

 

1833번: 고속철도 설계하기

첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에는 인접행렬 형태로 두 도시 사이에 고속철도를 설치할 때 드는 비용이 주어진다. 이 비용은 각각 10,000을 넘지 않는 자연수이다. 만약 비용이 음

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 모든 간선을 입력받고, 값이 음수이면 ans에 절댓값을 더해주고, 양수이면 arr 배열에 추가합니다.

 

2. arr 배열을 비용에 관하여 오름차순으로 정렬합니다.

 

3. arr 배열을 for문을 통해 돌면서 노드들을 이어주고, 비용을  ans에 더해주고, 이어진 노드들을 list에 저장합니다.

 

4. ans와 list.size()를 출력하고, 이어진 노드들을 차례대로 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
struct node {
    int u, v, w;
};
 
bool cmp(node left, node right)
{
    return left.w < right.w;
}
 
int N;
int ans;
vector<node> arr;
vector<pair<int, int>> list;
int vect[201];
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        vect[i] = i;
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            int cost;
            scanf("%d", &cost);
 
            if (i < j) {
                if (cost < 0) {
                    ans += -cost;
                    Union(i, j);
                }
                else if(cost>0) {
                    arr.push_back({ i,j,cost });
                }
            }
        }
    }
 
    sort(arr.begin(), arr.end(), cmp);
 
    for (auto& next : arr) {
        const int u = next.u;
        const int v = next.v;
        const int w = next.w;
 
        if (Find(u) != Find(v)) {
            list.push_back({ u,v });
            Union(u, v);
            ans += w;
        }
    }
 
    printf("%d %d\n", ans, (int)list.size());
 
    for (int i = 0; i < list.size(); i++) {
        printf("%d %d\n", list[i].first, list[i].second);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 7044번 - Bad Cowtractors (C++)  (0) 2023.03.19
[ 백준 ] 9372번 - 상근이의 여행 (C++)  (0) 2023.03.18
[ 백준 ] 1926번 - 그림 (C++)  (0) 2023.03.16
[ 백준 ] 18769번 - 그리드 네트워크 (C++)  (0) 2023.03.15
[ 백준 ] 9344번 - 도로 (C++)  (0) 2023.03.14

+ Recent posts

티스토리툴바