백준12918 정리정돈

작성일 | In

문제 링크

  • http://icpc.me/12918

사용 알고리즘

  • MCMF

풀이

y축 위에 물건을 놓아도 선대칭입니다.

각 물건에 대해 두 가지 중 한 가지 선택을 해야 합니다.

  1. 다른 물건 하나와 매칭해서 선대칭이 되도록 이동
  2. y축 위로 이동

1번의 경우 한 물건의 위치는 고정시키고 다른 물건 하나만 이동시켜도 최적해를 찾을 수 있다는 것은 직관적으로 알 수 있습니다. 그러므로 두 물건의 위치가 각각 $(x_i, y_i), (x_j, y_j)$라고 하면 $(x_j, y_j)$를 $(-x_i, y_i)$으로 이동시키면 됩니다. 이때의 이동 거리는 $\sqrt{(x_i+x_j)^2+(y_i-y_j)^2}$이 됩니다. 두 점이 각각 $\frac{1}{2}\sqrt{(x_i+x_j)^2+(y_i-y_j)^2}$ 만큼의 비용을 나눠서 부담한다고 생각해도 됩니다.

2번의 경우 $\vert x_i \vert$만큼 이동해야 합니다. $\frac{1}{2}\sqrt{(x_i+x_i)^2+(y_i-y_i)^2}$으로 표현할 수도 있습니다.

각 물건을 y축에 선대칭시켜서 새로운 물건을 하나씩 만들어준 뒤, x좌표가 음수인 물건을 $L_i$, x좌표가 양수인 물건을 $R_i$라고 합시다.
$L_i$와 $R_j$를 간선으로 이어주고 가중치를 (두 점 사이의 거리 / 2)로 설정한 이분 그래프를 만든 뒤, MCMF를 돌려주면 답을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define int long long
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

const int SZ = 222;
struct MCMF{
    using FlowType = int;
    using CostType = double;
    const CostType cost_max = 1e9;
    int s, t; //source, sink
    struct Edge{ int v, dual; FlowType c; CostType d; };
    vector<Edge> g[SZ];
    void addEdge(int s, int e, FlowType c, CostType d){
        g[s].push_back({e, (int)g[e].size(), c, d});
        g[e].push_back({s, (int)g[s].size()-1, 0, -d});
    }

    int inq[SZ]; CostType h[SZ]; //johnson's algorithm, spfa
    CostType dst[SZ]; //dijkstra
    void init(int _s, int _t){
        s = _s, t = _t;
        fill(h, h+SZ, cost_max);
        fill(dst, dst+SZ, cost_max);

        //johnson's algorithm with spfa
        queue<int> q; q.push(s); inq[s] = 1;
        while(q.size()){
            int now = q.front(); q.pop(); inq[now] = 0;
            for(auto i : g[now]){
                if(i.c && h[i.v] > h[now] + i.d){
                    h[i.v] = h[now] + i.d;
                    if(!inq[i.v]) inq[i.v] = 1, q.push(i.v);
                }
            }
        }

        for(int i=0; i<SZ; i++){
            for(auto &j : g[i]) if(j.c) j.d += h[i] - h[j.v];
        }

        //get shortest path DAG with dijkstra
        priority_queue<pair<CostType, int>> pq; pq.emplace(0, s); dst[s] = 0;
        while(pq.size()){
            int now = pq.top().y;
            CostType cst = -pq.top().x;
            pq.pop();
            if(dst[now] != cst) continue;
            for(auto i : g[now]){
                if(i.c && dst[i.v] > dst[now] + i.d){
                    dst[i.v] = dst[now] + i.d;
                    pq.emplace(-dst[i.v], i.v);
                }
            }
        }
        for(int i=0; i<SZ; i++) dst[i] += h[t] - h[s];
    }

    int chk[SZ], work[SZ];

    bool update(){ //update shortest path DAG in O(V+E)
        CostType mn = cost_max;
        for(int i=0; i<SZ; i++){
            if(!chk[i]) continue;
            for(auto j : g[i]){
                if(j.c && !chk[j.v]) mn = min(mn, dst[i] + j.d - dst[j.v]);
            }
        }
        if(mn == cost_max) return 0;
        for(int i=0; i<SZ; i++){
            if(!chk[i]) dst[i] += mn;
        }
        return 1;
    }
    FlowType dfs(int now, FlowType fl){
        chk[now] = 1;
        if(now == t) return fl;
        for(; work[now] < g[now].size(); work[now]++){
            auto &i = g[now][work[now]];
            if(!chk[i.v] && dst[i.v] == dst[now] + i.d && i.c){
                FlowType ret = dfs(i.v, min(fl, i.c));
                if(ret > 0){
                    i.c -= ret; g[i.v][i.dual].c += ret;
                    return ret;
                }
            }
        }
        return 0;
    }
    pair<CostType, FlowType> run(int _s, int _t){ //{cost, flow}
        init(_s, _t);
        CostType cst = 0; FlowType fl = 0;
        do{
            memset(chk, 0, sizeof chk);
            memset(work, 0, sizeof work);
            FlowType now;
            while((now = dfs(s, 1e9)) > 0){
                cst += dst[t] * now;
                fl += now;
                memset(chk, 0, sizeof chk);
            }
        }while(update());
        return {cst, fl};
    }
} mcmf;

int n; p a[222];

int sign(int x){
    if(x > 0) return 1;
    if(x) return -1;
    return 0;
}
double cst(p s, p e){
    int dx = s.x - e.x;
    int dy = s.y - e.y;
    return sqrt(dx*dx + dy*dy);
}

const int S = 220, T = 221;

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; for(int i=1; i<=n; i++) cin >> a[i].x >> a[i].y;
    for(int i=n; i; i--){
        a[i << 1] = a[i << 1 | 1] = a[i];
        a[i << 1 | 1].x *= -1;
    }
    for(int i=1; i<=n; i++){
        mcmf.addEdge(S, i << 1, 1, 0);
        mcmf.addEdge(i << 1 | 1, T, 1, 0);
    }
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
        mcmf.addEdge(i << 1, j << 1 | 1, 1, cst(a[i << 1], a[j << 1 | 1]) / 2.0);
    }
    auto t = mcmf.run(S, T);
    cout << fixed << setprecision(3) << t.x;
}