[4343번] Arctic Network

문제 출처 :

https://www.acmicpc.net/problem/4343

알고리즘 분석 :

문제 해결에 필요한 사항

1. 최소 스패닝 트리(MST) :: http://www.crocus.co.kr/733

2. 유니온 파인드(Union Find) :: http://www.crocus.co.kr/683

문제를 이해하는 과정이 중요하다.

예제 입력을 이용하여 문제를 이해해보자.

1
2 4
0 100
0 300
0 600
150 750

1은 테스트 케이스를 의미하고

2 4중 2는 위성 채널의 수를 의미, 4는 output의 수를 의미한다.

아래 4개의 값은 output이 존재하는 x,y의 위치를 의미한다.

결국 최소 스패닝 트리를 만들되, 모든 노드가 연결되지 않고, 위성 수만큼으로는 무선으로 연결이 가능하다는 의미이다.

위의 과정에서 보면 붉은색 선은 최소 스패닝 트리에 의해 연결된 간선들이고

푸른색 선은 위성수 2개를 이용하여 하나의 무선 간선을 만든 것이다.

따라서 이 정점들은 2개의 붉은선, 1개의 푸른선으로 의해 모두 연결이 되었고, 이때 최소 D는 212.13임을 알 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <memory.h>
 
using namespace std;
 
typedef pair<double, pair<int, int>> pdpii;
 
typedef struct _INFO_
{
    int x;
    int y;
}INFO;
 
INFO arr[501];
int parent[501];
int cnt;
 
int find(int u)
{
    if (u == parent[u])
        return u;
 
    return parent[u] = find(parent[u]);
}
 
void merge(int u, int v)
{
    u = find(u);
    v = find(v);
 
    if (u == v)
        return;
 
    // 유니온에 성공하면 outposts의 수를 1빼준다.
    cnt--;
    parent[u] = v;
}
 
int main()
{
    int tCase;
    scanf("%d", &tCase);
 
    while (tCase--)
    {
        // 초기화
        memset(arr, 0, sizeof(arr));
        for (int i = 1; i <= 500; i++)
            parent[i] = i;
 
        // 위성 수, output 수
        int s, p;
        scanf("%d %d", &s, &p);
 
        for (int i = 1; i <= p; i++)
            scanf("%d %d", &arr[i].x, &arr[i].y);
 
        // 최소 힙
        priority_queue<pair<double, pair<int, int>>> pq;
 
        for(int i = 1; i < p; i ++)
            for (int j = i + 1; j <= p; j++)
            {
                // x2, y2는 outpost 두개의 거리를 의미
                int x2 = (arr[i].x - arr[j].x)*(arr[i].x - arr[j].x);
                int y2 = (arr[i].y - arr[j].y)*(arr[i].y - arr[j].y);
                double len = sqrt(x2 + y2); // 두점 사이 거리
                pq.push(pdpii(-len, {i, j})); // 최소 힙으로 pq를 쓰기위해 -로 넣는다.
            }
 
        // cnt :: 필요한 outposts을 연결할 라디오 수
        cnt = p - s;
 
        double val;
        int idx1, idx2;
 
        while (cnt)
        {
            // 최소 스패닝 트리를 위해 가장 작은 값부터 연결
            val = -pq.top().first;
            idx1 = pq.top().second.first;
            idx2 = pq.top().second.second;
 
            pq.pop();
 
            merge(idx1, idx2);
        }
 
        // 최소 스패닝 트리에 의해 가장 작은 간선끼리 연결하여
        // 그때 마지막으로 연결된 간선의 값이 D로 결정된다.
        printf("%.2lf\n", val);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>