Участник:Kachanov vv/EC MODE

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/EC_MODE/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
 
 
using namespace std;
const int max_value = 1000010;
 
class Solver {
public:
    Solver(int N, double R, int W, double U, double V) :
            N(N), R(R), W(W), U(U), V(V) {}
 
    void init() {
        city.clear();
        roads.clear();
        for (int i = 0; i < max_value; i++) {
            parent[i] = i;
        }
        for (int i = 1; i <= N; i++) {
            cin >> x >> y;
            city.emplace_back(make_pair(x, y));
        }
        ans0 = 0;
        ans1 = 0;
    }
 
    void process() {
        calculateDistance();
        sort(roads.begin(), roads.end());
 
        components = N;
        for (pair<pair<double, int>, pair<int, int> > road: roads) {
            cost = road.first.first;
            type = road.first.second;
            from = road.second.first;
            to = road.second.second;
 
            unite(from, to);
            if (components == W || components == 1)
                break;
        }
    }
 
    int find(int a) {
        if (parent[a] != a) {
            parent[a] = find(parent[a]);
        }
        return parent[a];
    }
 
    void unite(int a, int b) {
 
        int u = find(a);
        int v = find(b);
        if (u == v)
            return;
        parent[u] = v;
        if (type == 0)
            ans0 += cost;
        else ans1 += cost;
        components--;
 
    }
 
    void calculateDistance() {
        double d, diff_x, diff_y;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                diff_x = city[i].first - city[j].first;
                diff_y = city[i].second - city[j].second;
                d = hypot(diff_x, diff_y);
                if (d <= R) {
                    cost = d * U;
                    type = 0;
                } else {
                    cost = d * V;
                    type = 1;
                }
                roads.emplace_back(make_pair(
                        make_pair(cost, type),
                        make_pair(i, j)));
            }
        }
    }
 
    void dump(int t) {
        cout << "Caso #" << t << ": " <<
             fixed << setprecision(3) << ans0 << " " << ans1 << endl;
    }
 
private:
    int components;
    int parent[max_value];
    int to, from, type, N, W;
    double x, y, cost, R, U, V;
    double ans0, ans1;
    vector<pair<double, double>> city;
    vector<pair<pair<double, int>, pair<int, int> > > roads;
};
 
int main() {
    int T, N, W;
    double R, U, V;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> N >> R >> W >> U >> V;
        Solver solver(N, R, W, U, V);
        solver.init();
        solver.process();
        solver.dump(t);
    }
}