[BOJ] 1414 : 불우이웃돕기

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

struct edg {
	int x, y, w;
	edg(int x, int y, int w) :x(x), y(y), w(w) {}
	bool operator <(edg A)const { return w < A.w; }
};

int n, pnt[101];
vector<edg> gph;

int find(int u) {
	if (u == pnt[u]) return u;
	return pnt[u] = find(pnt[u]);
}

void merge(int u, int v) {
	u = find(u), v = find(v);
	if (pnt[u] == pnt[v]) return;
	if (u > v) swap(u, v);
	pnt[u] = v;
}

int main() {
	int i, j, sum1 = 0, sum2 = 0;
	char str[101];
	scanf("%d", &n);
	for (i = 0; i < n; i++) pnt[i] = i;
	for (i = 0; i < n; i++) {
		scanf("%s", str);
		for (j = 0; j < n; j++) {
			int tmp = (int)str[j] + 1;
			if (str[j] >= 'a' && str[j] <= 'z') tmp -= 'a';
			if (str[j] >= 'A' && str[j] <= 'Z') tmp -= 'A' - 26;
			if (str[j] != '0') {
				sum1 += tmp;
				if (i != j) gph.push_back(edg(i, j, tmp));
			}
		}
	}
	sort(gph.begin(), gph.end());
	int cnt = 1;
	for (auto now : gph) {
		int x = now.x, y = now.y, w = now.w;
		if (find(x) != find(y)) merge(x, y), sum2 += w, cnt++;
	}
	if (cnt < n) printf("-1");
	else printf("%d", sum1 - sum2);

	return 0;
}