백준 6497 - 전력난

문제 링크입니다 https://www.acmicpc.net/problem/6497

6497번: 전력난

 

문제 조건

최소 스패닝 트리를 이용해 연결할 수 있는 최소 액수를 구한 다음 전체 액수에서 빼면 되는 문제였습니다.

 

문제 접근

 

1. M과 N을 입력을 받은후, X,Y,Z를 입력받고, 구조체 백터에다가 넣어준다. (Z 값을 maxi에다가 전부 더해준다)

2. 백터를 COST에 따라서 오름차순으로 정렬한다.

3. check배열의 i번째 칸은 i에서 출발하면 어디를 갈 수 있는지를 의미한다. 따라서 check[i] = i를 처음에 넣어준다.

4. 구조체 백터안에 있는 start와 finish를 Find()함수를 통해 어디를 갈 수 있는지를 찾는다.

5. 서로 향하는 곳이 다를 경우 check의 값을 바꾼 뒤에 mini 값에다가 cost를 더해준다. 

 

 

자세한 것은 코드를 참고해주세요!

 

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
using namespace std;


int m, n,maxi, mini;
bool fin = false;
typedef struct le {
    int start;
    int finish;
    int cost;
}le;
int check[200011];
vector<le> line;

bool cmp(le a, le b) {
    if (a.cost < b.cost) return true;
    return false;
}

void input(){
    cin >> m >> n;
    if (m == 0 && n == 0) {
        fin = true;
        return;
    }
    maxi = 0;
    mini = 0;
    line.clear();
    for (int i = 0; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        maxi += z;
        line.push_back({ x,y,z });
    }

}

int Find(int x) {
    if (check[x] == x) return x;
    else return check[x] = Find(check[x]);
}

void Union(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    check[xx] = yy;
}

void solve() {
    while (1) {
        input();
        if (fin == true) {
            break;
        }
        for (int i = 0; i < 200011; i++) {
            check[i] = i;
        }
        sort(line.begin(), line.end(), cmp);
        for (int i = 0; i < n; i++) {
            int x = Find(line[i].start);
            int y = Find(line[i].finish);
            if (x != y) {
                Union(x, y);
                mini += line[i].cost;
            }
        }
        cout << maxi - mini << "\n";
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요!