1251. [S/W 문제해결 응용] 4일차 - 하나로(D4)

서로 연결되어있는지 확인을 잘해야한다.

이부분은....다른블로그에 구현된거 가져다 썼었는데 나중에 직접 구현해봐야한다.

벡터에 점과점의 길이, 점1, 점2 이렇게 기록하고 계산하였다.

#include <stdio.h>
#include <memory.h>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
 
int connect[1001];
 
unsigned long long find_connect(unsigned long long a)
{
    if (a == connect[a]) 
        return a;
    return connect[a] = find_connect(connect[a]);
}
void Union(unsigned long long a, unsigned long long b) {
    a = find_connect(a);
    b = find_connect(b);
    if (a == b) 
        return;
    connect[b] = a;
}
unsigned long long L(unsigned long long x1, unsigned long long y1, unsigned long long x2, unsigned long long y2)
{
    unsigned long long result = ((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));
    return result;
}
 
int main(void) {
    int T;
    setbuf(stdout, NULL);
    scanf("%d\n", &T);
    for (int test_case = 1; test_case <= T; test_case++)
    {
        memset(connect, 0, sizeof(connect));
        
        int n;
        scanf("%d", &n);
        unsigned long long xy[2][1000];
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < n; j++)
            {
                scanf("%llu", &xy[i][j]);
                connect[j] = j;
            }
        }
        double e;
        scanf("%lf", &e);
        vector< tuple<unsigned long long, unsigned long long, unsigned long long> > v;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                v.push_back(make_tuple(L(xy[0][i], xy[1][i], xy[0][j], xy[1][j]), (unsigned long long)i, (unsigned long long)j));//i->j, 길이
            }
        }
        sort(v.begin(), v.end());
        unsigned long long ans = 0;
        for (auto it = v.begin(); it != v.end();it++) {
            
            unsigned long long x = get<1>((*it));
            unsigned long long y = get<2>((*it));
            if (find_connect(x) == find_connect(y))//이미 연결되어있는지 확인
                continue;
            ans += get<0>((*it));
            Union(x, y);
        }
        e = ans * e;
        printf("#%d %.0lf\n", test_case, e);
    }
    return 0;
}