[BOJ/C++] 1414 불우이웃돕기

다솜이가 기부할 수 있는 랜선 길이의 최댓값을 구해야합니다.

연결되어 있는 모든 랜선을 최소 비용만 남기고 기부할 수 있으므로

다솜이가 최대로 기부할 수 있는 랜선의 길이는

(모든 랜선의 길이 - 모든 컴퓨터를 연결할 수 있는 랜선의 최소 길이) 입니다

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>

using namespace std;

using int32 = long;
using int64 = long long;


typedef struct Edge
{
    int start, end, weight;

    bool operator > (const Edge& edge) const
    {
        return weight > edge.weight;
    }
};

static int N;
static priority_queue<Edge, vector<Edge>, greater<>> pq;
static vector<int> parent;
static int sum = 0;

void MST();
void Union(int a, int b);
int Find(int a);


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N;

    vector<string> input;
    vector<vector<int>> G;

    input.resize(N);
    G.resize(N + 1, vector<int>(N + 1, 0));
    parent.resize(N + 1, 0);

    for (int i = 1; i <=N; i++)
        parent[i] = i;

    for (int i = 0; i < N; i++)
        cin >> input[i];

    for(int i=0; i<N; i++)
    {
	    for(int j=0; j<N; j++)
	    {
	        if(input[i][j] >= 'a' && input[i][j] <= 'z')
	        {
                G[i+1][j+1] = input[i][j] - 'a' + 1;
	        }
            else if (input[i][j] >= 'A' && input[i][j] <= 'Z')
            {
                G[i+1][j+1] = input[i][j] - 'A' + 27;
            }
	    }
    }

    // 모든 랜선의 길이 구하기
    for(int i=1; i<=N; i++)
    {
        for (int j = 1; j <= N; j++)
            sum += G[i][j];
    }

    // 에지 리스트 구하기

    for(int i=1; i<=N; i++)
    {
	    for(int j=1; j<=N; j++)
	    {
            if (G[i][j] != 0 && i != j)
                pq.push({ i, j, G[i][j] });
	    }
    }

	MST();

    return 0;
}


void MST()
{
    int result = 0;
    int usedEdge = 0;
    while(!pq.empty())
    {
        Edge edge = pq.top();
        pq.pop();

        if(Find(edge.start) != Find(edge.end))
        {
            Union(edge.start, edge.end);
            usedEdge++;
            result += edge.weight;
        }
    }

    // 만약 연결할 수 없다면
    if (usedEdge < N - 1)
        cout << -1;
    else
        cout << sum - result;

}

void Union(int a, int b)
{
    a = Find(a);
	b = Find(b);

    if (a != b)
        parent[b] = a;
}


int Find(int a)
{
    if (parent[a] == a)
        return a;

    return parent[a] = Find(parent[a]);
}