[백준] 2679 맨체스터의 도로

문제 링크

http://icpc.me/2679

2679번: 맨체스터의 도로

풀이

네트워크 플로우를 기반으로 하고, 우선순위 큐를 이용한 풀이와 이분 탐색을 이용한 풀이가 있다.

차의 개수는 네트워크 플로우를 이용하면 쉽게 구할 수 있지만, 길 1개를 이용할 때의 최대 개수는 구하기 어렵다.

일반적인 네트워크 플로우처럼 경로를 고른다면, 경로를 고르는 순서에 따라 어떤 길에 한 번에 보낼 수 있는 최대를 보내지 않을 수 있다. 그렇기 때문에 다른 처리를 해줘야 한다.

 

우선순위 큐 풀이

bfs를 이용하여 가장 큰 경로들을 고르는 과정에서 다익스트라스러운? 방법을 이용하여 경로를 고르면 된다.

경로들 중 용량이 가장 작은 용량을 최대 힙에 관리하면 한번 보낼 때마다 보낼 수 있는 가장 많은 flow를 보내기 때문에 이 보내는 flow값들 중에 최댓값이 무조건 존재하게 된다.

 

이분 탐색 풀이

그냥 네트워크 플로우를 이용하고 단일 경로 부분만 이분 탐색하면 된다.

문제를 결정문제로 바꿔서 파라매틱 서치를 이용하면 된다.

길 하나만 이용하여 소스-> 싱크로 k만큼의 flow가 갈 수 있는지는 dfs를 이용하여 단일 경로에 최소 용량이 k이상인 경로가 있는지 쉽게 결정할 수 있다.

또한 k만큼 flow가 갈 수 있다면 k보다 작은 flow는 무조건 갈 수 있다는 것은 증명을 해보지 않아도 직관적으로 갈 수 있다.

그렇기 때문에 어느 시점부터 k만큼의 용량은 갈 수 없고 그보다 큰 용량 또한 갈 수 없을 것이다. 그렇기 때문에 어느 경계를 기준으로 true false가 나뉘게 되고 이분 탐색을 이용하여 그 경계를 구할 수 있다.

 

코드

우선순위 큐

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

struct Edge {
    int to, cap, flow;
    Edge *rev;
    int spare() { return cap - flow; }
    void add_flow(int f) {
        this->flow += f;
        rev->flow -= f;
    }
};

constexpr int N = 1002;
vector<Edge *> adj[N];
int par[N];
Edge *path[N];
int mx;

void add_edge(int u, int v, int c) {
    Edge *uv = new Edge({v, c, 0, nullptr});
    Edge *vu = new Edge({u, 0, 0, nullptr});
    uv->rev = vu;
    vu->rev = uv;
    adj[u].push_back(uv);
    adj[v].push_back(vu);
}

void init() {
    for (int i = 0; i < N; i++) adj[i].clear();
    mx = 0;
}

int network_flow(int src, int sink) {
    int ret = 0;
    while (true) {
        memset(par, -1, sizeof(par));
        priority_queue<pair<int, int>> q;
        q.push({1e8, src});
        while (!q.empty() && par[sink] == -1) {
            auto [d, cur] = q.top(); q.pop();
            for (auto &e : adj[cur]) {
                int nxt = e->to;
                if (e->spare() > 0 && par[nxt] == -1) {
                    q.push({min(d, e->cap), nxt});
                    par[nxt] = cur;
                    path[nxt] = e;
                    if (nxt == sink) break;
                }
            }
        }
        if (par[sink] == -1) break;
        int mn = 1e9;
        for (int i = sink; i != src; i = par[i]) {
            mn = min(mn, path[i]->spare());
        }
        for (int i = sink; i != src; i = par[i]) {
            path[i]->add_flow(mn);
        }
        mx = max(mn, mx);
        ret += mn;
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int tc; cin >> tc;
    while (tc--) {
        init();
        int n, e, a, b; cin >> n >> e >> a >> b;
        for (int i = 0; i < e; i++) {
            int u, v, w; cin >> u >> v >> w;
            add_edge(u, v, w);
        }
        int maxflow = network_flow(a, b);
        printf("%.3f\n", 1.0 * maxflow / mx);
    }
}

이분 탐색

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

struct Edge {
    int to, cap, flow;
    Edge *rev;
    int spare() { return cap - flow; }
    void add_flow(int f) {
        this->flow += f;
        rev->flow -= f;
    }
};

constexpr int N = 1002;
vector<Edge *> adj[N];
int par[N];
Edge *path[N];
int n, e, src, sink; 
bool visited[N];

void add_edge(int u, int v, int c) {
    Edge *uv = new Edge({v, c, 0, nullptr});
    Edge *vu = new Edge({u, 0, 0, nullptr});
    uv->rev = vu;
    vu->rev = uv;
    adj[u].push_back(uv);
    adj[v].push_back(vu);
}

void init() {
    for (int i = 0; i < N; i++) adj[i].clear();
}

int network_flow(int src, int sink) {
    int ret = 0;
    while (true) {
        memset(par, -1, sizeof(par));
        queue<int> q;
        q.push(src);
        while (!q.empty() && par[sink] == -1) {
            int cur = q.front(); q.pop();
            for (auto &e : adj[cur]) {
                int nxt = e->to;
                if (e->spare() > 0 && par[nxt] == -1) {
                    q.push(nxt);
                    par[nxt] = cur;
                    path[nxt] = e;
                    if (nxt == sink) break;
                }
            }
        }
        if (par[sink] == -1) break;
        int mn = 1e9;
        for (int i = sink; i != src; i = par[i]) {
            mn = min(mn, path[i]->spare());
        }
        for (int i = sink; i != src; i = par[i]) {
            path[i]->add_flow(mn);
        }
        ret += mn;
    }
    return ret;
}

int check(int cur, int k) {
    if (cur == sink) return true;
    visited[cur] = true;
    int ret = 0;
    for (auto &e : adj[cur]) {
        if (e->cap >= k && !visited[e->to]) {
            ret += check(e->to, k);
        }
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int tc; cin >> tc;
    while (tc--) {
        init();
        cin >> n >> e >> src >> sink;
        for (int i = 0; i < e; i++) {
            int u, v, w; cin >> u >> v >> w;
            add_edge(u, v, w);
        }
        int maxflow = network_flow(src, sink);
        int l = -1, r = maxflow + 1;
        while (l + 1 < r) {
            memset(visited, 0, sizeof(visited));
            int mid = l + r >> 1;
            if (check(src, mid)) l = mid;
            else r = mid;
        }
        printf("%.3f\n", 1.0 * maxflow / l);
    }
}