AOJ 2724 - Laser Cutter

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2724

解法

結論を言えば、最小重み二部マッチングに帰着できる。

線分の交点と端点が頂点になった有向グラフを考えると、考えるべき問題は「いくつか辺を追加することで、最小重みのオイラーグラフを作る」になる。
辺を追加するとしたら、線分の端点同士（終点 -> 始点) を考えるだけで良い。
実際、端点以外での交点は、入次数と出次数が等しくなるようにしかならないためである。
したがって、端点同士でマッチングを取れば良いことがわかる。
（一応言っておくと、交点を経由するのは回り道でしかないのでありえない。）

最小重み二部マッチングは最小費用流やハンガリアン法で解けて、O(N^3logN) か O(N^3) となる。
最小費用流で解くときは、重みが整数値じゃないので、ポテンシャルの判定式に eps をつけないとバグるから気をつけること。

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
constexpr double eps = 1e-10;

struct edge {
    int to, rev, cap;
    double cost;
    edge(int t, int c, double ct, int r) : to(t), rev(r), cap(c), cost(ct) {}
};
using graph = vector<vector<edge>>;

void add_edge(graph& g, int from, int to, int cap, double cost) {
    g[from].emplace_back(to, cap, cost, g[to].size());
    g[to].emplace_back(from, 0, -cost, g[from].size() - 1);
}

double min_cost_flow(graph& g, int s, int t, int f) {
    using P = pair<double, int>;
    const double inf = 1e18;
    double res = 0;
    vector<double > h(g.size()), dist(g.size());
    vector<int> prevv(g.size()), preve(g.size());
    while(f > 0) {
        priority_queue<P, vector<P>, greater<>> que;
        fill(begin(dist), end(dist), inf);
        dist[s] = 0;
        que.emplace(0, s);
        while(!que.empty()) {
            const auto cur_d = que.top().first;
            const int v = que.top().second;
            que.pop();
            if(dist[v] < cur_d) continue;
            for(int i = 0; i < (int)g[v].size(); ++i) {
                auto& e = g[v][i];
                if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to] + eps) {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v;
                    preve[e.to] = i;
                    que.emplace(dist[e.to], e.to);
                }
            }
        }
        if(dist[t] == inf) return -1;
        for(int v = 0; v < (int)g.size(); ++v) {
            h[v] += dist[v];
        }

        auto d = f;
        for(int v = t; v != s; v = prevv[v]) {
            d = min(d, g[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += d * h[t];
        for(int v = t; v != s; v = prevv[v]) {
            auto& e = g[prevv[v]][preve[v]];
            e.cap -= d;
            g[v][e.rev].cap += d;
        }
    }
    return res;
}

int main() {
    int n; cin >> n;
    int ix, iy; cin >> ix >> iy;
    vector<int> sx(n), sy(n), gx(n), gy(n);
    for(int i = 0; i < n; ++i) {
        cin >> sx[i] >> sy[i] >> gx[i] >> gy[i];
    }

    double ans = 0;
    for(int i = 0; i < n; ++i) {
        ans += hypot(gx[i] - sx[i], gy[i] - sy[i]);
    }
    graph g(n * 2 + 2);
    const int src = n * 2, sink = n * 2 + 1;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            add_edge(g, i, j + n, 1, hypot(sx[j] - gx[i], sy[j] - gy[i]));
        }
        add_edge(g, src, i, 1, 0);
        add_edge(g, i + n, sink, 1, 0);
    }
    ans += min_cost_flow(g, src, sink, n);

    cout << fixed << setprecision(10) << ans << endl;
}