백준 1922 네트워크 연결

문제 URL : https://www.acmicpc.net/problem/1922

1922번: 네트워크 연결

 

문제접근법 : 최소스패닝 트리 문제입니다.

크루스칼 알고리즘을 이용하는 기초적인 문제입니다. 

 

소스코드 : 

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

//By 콩순이냉장고 #include <vector> #include <algorithm> #include <iostream> #include <queue> #include <fstream> using namespace std; vector<pair<int, pair<int, int>>> v; int n, e; int parent[1001];   int find(int idx) {     if (parent[idx] == idx)         return idx;     return parent[idx] = find(parent[idx]); } bool sameparent(int &idx1, int &idx2) {     idx1 = find(idx1);     idx2 = find(idx2);     return idx1 == idx2; } void Union(int idx1, int idx2) {     if (idx1 != idx2)         parent[idx2] = idx1; } int main(void) {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     cin >> n >> e;     int sum = 0;     for (int i = 0; i < e; i++)     {         int a, b, c;         cin >> a >> b >> c;         v.push_back({ c, { a, b } });     }     sort(v.begin(),v.end());     for (int i = 1; i <= n; i++){         parent[i] = i;     }       for (int i = 0; i < e; i++)     {         int left = v[i].second.first;         int right = v[i].second.second;         if (!sameparent(left, right))         {             sum += v[i].first;             Union(left, right);         }     }       cout << sum << endl; } Colored by Color Scripter

cs

 

궁금한점 혹은 모르는점이 있다면 언제든지 댓글을 이용해주시길 바랍니다.