UVA534 Frogger

Graph, Union Find, Kruskal, dijkstra

출처: UVA UUVA534 Frogger

       zoj
       poj

SOL)
여러 방법으로 풀 수있는 문제
크루스칼, Union find를 이용하여 해결하였다.


[-] Collapse

#include<stdio.h>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
int Num;
struct pos{
    double x, y;
}vertex[200];
struct Union_Find{
    vector<int> parent, rank;
    Union_Find(int n) :parent(n), rank(n){
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }
    int find(int u){
        if (parent[u] == u) return u;
        return find(parent[u]);
    }
    bool merge(int u, int v){
        u = find(u), v = find(v);
        if (u == v) return false;
        if (rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if (rank[u] == rank[v]) rank[v]++;
        return true;
    }
};
int adj[200][200];
double result;
Union_Find uf(1);
priority_queue< pair < double, int > >pq;

double dis(int l, int r){
    double x1, x2, y1, y2;
    x1 = vertex[l].x;
    x2 = vertex[r].x;
    y1 = vertex[l].y;
    y2 = vertex[r].y;
    return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2) * (y1 - y2));
}
void init(){
    for (int i = 0; i < Num; i++){
        for (int j = 0; j < Num; j++){
            if (i != j) adj[i][j]++;
        }
    }
    uf = Union_Find(Num);
    pq = priority_queue< pair < double, int > > ();
    pq.push(make_pair(0, 0));
    result = 0;
}
int main(){
    //freopen("input.txt", "r", stdin);
    int testCase = 0;
    while (true){
        scanf("%d", &Num);
        if (Num == 0) break;
        init();
        for (int i = 0; i < Num; i++){
            scanf("%lf%lf", &vertex[i].x, &vertex[i].y);
        }
        while(uf.find(0) != uf.find(1)){
            int here = pq.top().second;
            double cost = -pq.top().first;
            pq.pop();
            uf.merge(0, here);
            if (result < cost)
                result = cost;
            for (int there = 0; there < Num; there++){
                if (uf.find(here) != uf.find(there)){
                    pq.push(make_pair(-dis(here, there), there));
                }
            }
        }
        printf("Scenario #%d\n", ++testCase);
        printf("Frog Distance = %.3lf\n\n", result);
    }
    return 0;
}