AOJ 2224 Save your cat (JAG 夏合宿 2010 day4-C) (500 点)

これ面白い！！！！！！！！　好き！！！！！！！

問題へのリンク

問題概要

平面上に 個の点の座標 と、それらを結ぶ 本の線分がある。 線分のある部分は通過ができないので、線分に囲われた領域とその外側の領域とは行き来することができない。

そこでいくつかの線分を取り除くことにより、平面上の任意の点を行き来できるようにしたい。取り除くべき線分の長さの最小値を求めよ。

制約

• 
• どの 2 つの線分も端点以外での共有点を持たない
• どの点も、どの線分の内点とはならない

考えたこと

与えれた平面グラフから最小コストの枝を取り除くことで、サイクルをすべて壊したいという問題。つまり

• 壊した後のグラフにはサイクルがない

↓

• 壊した後のグラフは元のグラフの全域木 (の部分集合) である

壊した後のグラフはなるべくコストが大きいものを残したい。したがって、元のグラフの最小全域木ならぬ最大全域木を求めればよい。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

struct UnionFind {
    vector<int> par, rank;
    
    UnionFind(int n = 210000) { init(n); }
    void init(int n = 210000) {
        par.resize(n); rank.resize(n);
        for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0;
    }
    
    int root(int x) {
        if (par[x] == x) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        return true;
    }
};

typedef pair<int,int> pint;
typedef pair<double,pint> Edge;

int main() {
    int N, M; cin >> N >> M;
    vector<double> x(N), y(N); for (int i = 0; i < N; ++i) cin >> x[i] >> y[i];
    vector<Edge> edges;
    double all = 0;
    for (int i = 0; i < M; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        double dis = sqrt((x[u]-x[v])*(x[u]-x[v]) + (y[u]-y[v])*(y[u]-y[v]));
        edges.push_back(Edge(dis, pint(u, v)));
        all += dis;
    }
    sort(edges.rbegin(), edges.rend());
    UnionFind uf(N);
    double hosyu = 0;
    for (auto e : edges) {
        int u = e.second.first, v = e.second.second;
        if (uf.issame(u, v)) continue;
        hosyu += e.first;
        uf.merge(u, v);
    }
    cout << fixed << setprecision(10) << all - hosyu << endl;
}