BOJ 11710 Cost Performance Flow
sorohue가 PS하는 블로그
문제 링크입니다.
문제 요약
주어진 방향 그래프의 $s$-$t$ 유량 문제를 고려합니다. 유량 $f$를 흘릴 때의 최소 코스트를 $C(f)$, 최대 유량을 $M$이라 할 때, ${ C(f) }^2 + (M-f)^2$의 최솟값을 구하세요.
MCMF 관찰하기
MCMF의 작동 원리를 간단히 살펴보면 다음과 같습니다.
- SPFA 등의 최단 경로 알고리즘으로 코스트 합이 최소인 증가 경로를 하나 찾습니다.
- 해당 증가경로에 플로우를 흘립니다.
이 과정에서 우리가 찾는 최단 경로의 코스트를 현재의 플로우 값 $f$에서 $C(f)$의 기울기로 해석할 수 있습니다. 이를 바탕으로 $C(f)$의 그래프를 그려보면 여러 개의 선형 함수를 이어붙인 개형의 그래프를 얻을 수 있습니다. 두 선형 함수가 만나는 지점 = MCMF 과정 상에서 한 증가 경로를 찾아 플로우를 흘린 뒤의 점 $(f, C(f))$를 꼭짓점이라 부릅시다.
그래프 상의 연속한 세 꼭짓점 $p = (f_p, C(f_p))$, $q = (f_q, C(f_q))$, $r = (f_r, C(f_r))$에 대해 $\overline{pq}$의 기울기를 $c_1$, $\overline{qr}$의 기울기를 $c_2$라 합시다.
이제 $c_1 \gt c_2$를 가정합니다. 그러면 $p$에서의 유량 그래프 $G_p$와 $r$에서의 유량 그래프 $G_r$의 차이를 새로운 증가 경로로 생각하여 플로우를 흘릴 수 있습니다. 이는 $C(f)$의 그래프 상에서 두 점 $p$와 $r$을 잇는 선분으로 표현되고, $q$의 아래를 지납니다. 점 $q$는 유량이 $f_q$일 때의 코스트 최솟값을 표현해야 하므로 아래로 지나도록 유량을 흘리는 방법이 존재함은 MCMF의 조건에 위배됩니다.
따라서 귀류법에 의해 $c_1 \lt c_2$이고, $C(f)$는 아래로 볼록한 함수입니다.
문제 풀기
$f$를 $M-f$로 뒤집으면 문제에서 주어진 퍼포먼스 함수 $B$를 $B(f) = f^2 + { C(f) }^2$로 나타낼 수 있습니다. 따라서 원래의 문제는 원점이 중심이고 $C$의 그래프에 접하는 원의 최소 반지름(의 제곱)을 구하는 문제가 됩니다. 각 선분을 직선으로 확장해 기하학적으로 접하는 원의 존재성을 판정하거나 양 끝점에서의 미분값을 이용해 접하는 원을 찾거나 하는 방법으로 각 선분 조각마다 ${\cal O}(1)$에 해당 선분 조각에 접하는 원의 최소 반지름을 구할 수 있습니다.
코드
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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using i128 = __int128;
const ll INF = 1234123412341234LL;
ll cap[234][234], flow[234][234]; int par[234];
ll d[234][234], dist[234]; bool vis[234];
vector<int> e[234];
const int source = 0, sink = 222;
vector<pll> f;
i128 gcd(i128 a, i128 b){
return b ? gcd(b, a%b) : a;
}
void add_edge(int u, int v, ll c, ll w){
cap[u][v] = c; e[u].push_back(v); e[v].push_back(u);
d[u][v] = w; d[v][u] = -w;
}
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
int n, m, s, t; cin >> n >> m >> s >> t; add_edge(source, s*2-1, INF, 0); add_edge(t*2, sink, INF, 0);
while(m--){int u, v, c, w; cin >> u >> v >> c >> w; add_edge(u*2, v*2-1, c, w);}
for(int i = 1; i <= n; i++) add_edge(i*2-1, i*2, INF, 0);
ll totw = 0; ll ans = 0;
f.push_back({0,0});
while(1){
memset(par, -1, sizeof(par));
memset(dist, 64, sizeof(dist));
memset(vis, 0, sizeof(vis));
queue<int> q;
dist[source] = 0;
vis[source] = 1;
q.push(source);
while(q.size()){
int now = q.front(); q.pop(); vis[now] = 0;
for(auto& nxt : e[now]){
if(cap[now][nxt] > flow[now][nxt] && dist[nxt] > dist[now]+d[now][nxt]){
dist[nxt] = dist[now]+d[now][nxt];
par[nxt] = now;
if(!vis[nxt]){
q.push(nxt);
vis[nxt] = 1;
}
}
}
}
if(par[sink] < 0) break;
ll cost = INF;
for(int i = sink; i != source; i = par[i]) cost = min(cost, cap[par[i]][i]-flow[par[i]][i]);
for(int i = sink; i != source; i = par[i]){
totw += cost*d[par[i]][i];
flow[par[i]][i] += cost;
flow[i][par[i]] -= cost;
}
ans += cost;
f.push_back({ans, totw});
}
if(f.size() == 1) return !(cout << "0/1\n");
i128 bunza = min(ans, totw); bunza *= bunza; i128 bunmo = 1;
for(auto& [F, W] : f) if(bunza > (i128)(ans-F)*(ans-F)+(i128)W*W) bunza = (i128)(ans-F)*(ans-F)+(i128)W*W;
for(int i = 1; i < f.size(); i++){
i128 df = f[i].first - f[i-1].first;
i128 dc = f[i].second - f[i-1].second;
i128 t = dc/df;
if(f[i-1].first-ans+t*f[i-1].second <= 0 && f[i].first-ans+t*f[i].second >= 0){
i128 delta_bunza = ans-f[i-1].first-t*f[i-1].second;
i128 delta_bunmo = t*t+1;
i128 g = gcd(delta_bunza, delta_bunmo); delta_bunza /= g; delta_bunmo /= g;
i128 tmp1 = (i128)ans*delta_bunmo-(i128)f[i-1].first*delta_bunmo-delta_bunza; tmp1 *= tmp1;
i128 tmp2 = (i128)f[i-1].second*delta_bunmo + t*delta_bunza; tmp2 *= tmp2;
i128 ans_bunza = tmp1+tmp2; i128 ans_bunmo = delta_bunmo*delta_bunmo;
g = gcd(ans_bunza, ans_bunmo); ans_bunza /= g; ans_bunmo /= g;
if(bunza*ans_bunmo > bunmo*ans_bunza) bunza = ans_bunza, bunmo = ans_bunmo;
}
}
cout << (ll)bunza << '/' << (ll)bunmo << '\n';
}