[백준 10319번] [네트워크 플로우 / 정점 분할] 좀비 아포칼립스

상당히 재밌게 풀은 문제이다.

 

이 문제를 풀기위해서는 여러 도로들을 거치면서 사람이 지나갈 수 있는 정도를 이해해야한다.

예를 들어 1번에서 2번으로 가기 위한 간선은 매 단위시간마다 2명이 들어설 수 있고 지나가려면 단위 시간 3이 필요하고

2번에서 3번으로 가기 위한 간선은 매 단위시간마다 1명이 들어설 수 있고 지나가려면 단위 시간 5가 필요하다고 하자.

 

그러면 1번에서 3번으로 가기 위해서는 간선 (1,2)와 (2,3)을 거쳐가야하는데 이 과정에서 두번째 간선의 유입량이 1로써 제일 작으므로 사실상 단위 시간당 3번으로 빠져나오는 양은 1이다.

 

즉, 빠져나오는 양은 간선의 단위 시간 당 들어올 수 있는 사람의 수의 최솟값이다.

 

사람의 유입되고 그것을 산출하는 방식이므로 Network flow로 이해할 수 있고

단위 시간 당 들어올 수 있는 사람의 수는 사실상 capacity로 이해할 수 있다.

 

다만, 이 문제가 특이한 지점은 앞서 언급한 것처럼 단위시간이 존재한다는 것이다.

가장 많은 인원을 병원으로 내보내기 위해서는 가장 시간이 덜 걸리는 간선을 타고 이동해야하는데 기존의 일반적으로 다루는 Network flow로는 이 지점을 처리할 수 없다.

 

해결이 안되는 이유는 이동하는데 걸리는 시간에 대한 고려 없이 capacity만 가지고 처리할 수 없기 때문이다. 이러한 측면에서 간선을 분할하는 방식을 생각할 수 있다.

 

간선을 cost만큼 분할하고 Edmonds-Karp 방식을 활용하여 최소 bfs로 계속해서 갱신시킨다는 것의 의미는 최단 시간안에 병원에 갈 수 있는 것을 찾는 것과 동치이다.(결과적으로 BFS를 통해 가장 최단 경로를 찾게 될 것이고, 경로를 한번 타고 이동할 때마다 시간이 1 증가한다는 점을 이용하면 무조건 BFS를 통해 나오는 결과는 최단 시간이 걸리는 Augmenting path라고 보장할 수 있다.)

따라서 해당 augmenting path를 통해 이동할 수 있는 사람의 숫자는 (s - 해당 간선을 통해 병원을 갈 수 있는 최소 시간 + 1) * capacity이다.

 

위의 내용을 활용하여 모든 augmenting path를 구하고 max_flow를 구해주면 된다.

 

다만, 위의 간선을 cost만큼 분할하기 위해서 좀 메모리를 강제로 많이 잡아먹기는 했다.(이 부분은 개선할 수 있는 방향성이 충분히 존재할 것 같으니 고민해보도록 하자.)

 

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
typedef pair<int, int> pii;
const int INF = 987654321;
const int MAX_N = 1002001;
int n;
int start, g, s; // i : 처음에 있는 장소(Source), g : 사람의 수, s : 감염까지 걸리는 시간

struct edge{
    int from, to, capacity, flow;
    edge* reverse_edge;
    edge(int u, int v, int c) : from(u), to(v), capacity(c), flow(0)
    {}
    int residual(){
        return capacity - flow;
    }
    void add_flow(int amount){
        flow += amount;
        reverse_edge -> flow -= amount;
    }
};

vector<edge*> adj[MAX_N];

void add_edge(int u, int v, int c, bool dir = true){
    edge* e1 = new edge(u, v, c);
    edge* e2 = new edge(v, u, dir ? 0 : c);
    e1 -> reverse_edge = e2;
    e2 -> reverse_edge = e1;
    adj[u].push_back(e1);
    adj[v].push_back(e2);
}

int networkFlow(int source, int sink){
    int max_flow = 0;
    while(true){
        vector<edge*> parent(MAX_N, nullptr);
        queue<pii> q;
        q.push(make_pair(source, 0));
        int cost_temp;
        while(!q.empty() && parent[sink] == nullptr){
            int here = q.front().first;
            int cost = q .front().second;
            q.pop();
            for(int i = 0; i < adj[here].size(); i++){
                int there = adj[here][i] -> to;
                if(adj[here][i] -> residual() > 0 && parent[there] == nullptr){
                    q.push(make_pair(there, cost + 1));
                    parent[there] = adj[here][i];
                }
                if(parent[sink] != nullptr){
                    cost_temp = cost;
                }
            }
        }
        if(parent[sink] == nullptr) break;
        if(cost_temp > s) break; // 이미 bfs에서 만족하는 케이스를 넘은 경우 (무조건 뒤는 더 cost가 크므로 break`)
        int amount = INF;
        for(int p = sink; p != source; p = parent[p] -> from){
            amount = min(amount, parent[p] -> residual());
        }
        for(int p = sink; p != source; p = parent[p] -> from){
            parent[p] -> add_flow(amount);
        }
        max_flow += (s - cost_temp + 1) * amount;
    }
    return max_flow;
}

int main(void){
    fastio;
    int test_case;
    cin >> test_case;

    for(int i = 0; i < test_case; i++){
        cin >> n;
        cin >> start >> g >> s;
        int m; // 병원~~
        cin >> m;
        for(int j = 0; j < m; j++){
            int temp;
            cin >> temp;
            add_edge(temp, 1002000, INF);
        }

        int edge_num;
        cin >> edge_num;

        for(int j = 0; j < edge_num; j++){
            int from, to, capacity, cost;
            cin >> from >> to >> capacity >> cost;
            if(cost == 1){
                add_edge(from, to, capacity);
                continue;
            } 
            add_edge(from, 1001 + 1000 * j, capacity);
            for(int k = 0; k < cost - 2; k++){
                add_edge(1001 + 1000 * j + k, 1001 + 1000 * j + k + 1, capacity);
            }
            add_edge(1001 + 1000 * j + cost - 2, to, capacity);
        }
        int result_value = networkFlow(start, 1002000);
        if(result_value > g) cout << g << "\n";
        else cout << result_value << "\n";
        for(int i = 0; i < MAX_N; i++){
            adj[i].clear();
        }
    }

    return 0;
}