백준19855 3분 그래프 리턴즈

작성일 | In

문제 링크

  • http://icpc.me/19855

사용 알고리즘

  • MCMF
  • 다익스트라

시간복잡도

  • $O(N \log N)$

풀이

한 지점에 3개의 구간이 있다면 사이클이 만들어집니다. 그러므로 각 지점을 2개 이하의 구간만 지나도록 구간을 적절히 선택하는 문제라고 생각할 수 있습니다. 2개 이하 조건은 어려워보이니 1개 이하 조건 문제를 먼저 풀어봅시다.

각 지점에 최대 1개의 구간만 지나도록 구간을 선택하는 것은, $0, 1, 2, \cdots , 500\,000$까지의 지점을 만들어서 한 칸씩 뒤로 이동하다가, 구간 $[s, e]$를 선택하면 $s-1$에서 $e$로 점프하는 것이라고 생각할 수 있습니다. 이때 점프하는 구간의 가중치의 합을 최대화하면 됩니다. 이는 $i-1$에서 $i$로 가는 가중치가 0인 간선과, $s-1$에서 $e$로 가는 가중치가 $t_i$인 간선을 만든 다음 0에서 50만으로 가는 최장 경로를 구하는 것과 동일합니다. DAG이므로 DP를 이용해 $O(N)$에 구할 수 있습니다.

2개 이하 조건은 MCMF로 해결할 수 있습니다. 0에서 50만까지 유량을 2만큼 흘릴 때의 최대 가중치를 구하면 됩니다. 이때 $i-1$에서 $i$로 가는 간선의 용량은 $\infty$, $s-1$에서 $e$로 가는 간선의 용량은 1입니다. MCMF를 그대로 구현하면 이므로 시간 초과를 받게 되므로 그래프의 형태를 이용해 최적화해야 합니다.

DAG이므로 첫 유량은 DP를 이용해 $O(N)$에 구할 수 있습니다. 첫 유량에서 사용한 간선을 뒤집어야 하는데, 간선을 뒤집으면 DAG 성질이 없어지기 때문에 DP를 사용하지 못하고, 음수 가중치가 있기 때문에 최단 경로를 빠르게 찾지도 못합니다.

MCMF에서 Johnson’s Algorithm을 이용해 음수 가중치를 없애는 방법은 방법은 잘 알려져 있습니다. 마침 첫 번째 유량을 구하면서 각 정점까지의 최단 거리를 구했기 때문에 추가적인 과정 없이 음수 가중치를 없앨 수 있습니다. 음수 가중치를 없앤 다음, Dijkstra’s Algorithm을 이용하면 두 번째 유량도 빠르게 찾을 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PLL = pair<ll, ll>;
constexpr int S = 500'000;

int N;
vector<PLL> G[505050];
set<PLL> E[505050];
ll C[505050], D[505050], P[505050], R;

void DP(){
    queue<int> Q;
    memset(P, -1, sizeof P);
    memset(D, 0x3f, sizeof D); D[0] = 0;
    for(int i=0; i<=S; i++) if(!C[i]) Q.push(i);
    while(Q.size()){
        int v = Q.front(); Q.pop();
        for(auto [i,w] : G[v]){
            if(D[i] > D[v] + w) D[i] = D[v] + w, P[i] = v;
            if(!--C[i]) Q.push(i);
        }
    }
    R += D[S];
}

void ReversePath(){
    for(int i=S; i!=0; i=P[i]) E[P[i]].emplace(i, D[i] - D[P[i]]);
    vector<PLL> res;
    for(int i=0; i<=S; i++){
        for(const auto &j : G[i]) if(i + 1 == j.first && j.second == 0 || !E[i].count(j)) res.push_back(j);
        swap(G[i], res); res.clear();
    }
    for(int i=0; i<=S; i++){
        for(const auto &[j,w] : E[i]) G[j].emplace_back(i, -w);
    }
}

void Johnson(){
    for(int i=0; i<=S; i++) for(auto &[j,w] : G[i]) w += D[i] - D[j];
}

void Dijkstra(){
    R += D[S] - D[0];
    memset(D, 0x3f, sizeof D);
    priority_queue<PLL, vector<PLL>, greater<>> Q;
    Q.emplace(D[0]=0, 0);
    while(Q.size()){
        auto [c,v] = Q.top(); Q.pop();
        if(c > D[v]) continue;
        for(auto [i,w] : G[v]) if(D[i] > c + w) Q.emplace(D[i]=c+w, i);
    }
    R += D[S];
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(ll i=1,s,e,x; i<=N; i++) cin >> s >> e >> x, G[s-1].emplace_back(e, -x), C[e]++;
    for(int i=1; i<=S; i++) G[i-1].emplace_back(i, 0), C[i]++;
    DP(); ReversePath(); Johnson(); Dijkstra();
    cout << -R;
}