취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 18134번 문제인 치삼이의 대모험이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/18134 

주어진 문제의 답이 되는 경로를 찾는 것은 H에서 T로 가는, vertex-disjoint하고 가중치의 총합이 최소인 두 경로의 그 가중치의 총합을 구하는 문제로 생각할 수 있다.

이는 주어진 그래프에서 각 에지와 꼭짓점(H와 T 제외)에 허용된 유량을 1, 각 에지의 비용을 L이라 할 때 H에서 T로 2의 유량을 최소비용으로 흘리는 문제로 생각할 수 있다. MCMF 문제를 해결하는 알고리즘을 이용해 문제를 해결해주자.

아래는 제출한 소스코드이다.

#define NODE 2002
#define INF 1000000007
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int source = 0, sink = 2001;
int edge[NODE][NODE], cost[NODE][NODE];
vector<int> G[NODE];

int par[NODE];
int stepcost[NODE];
int inque[NODE];

pair<int, int> MCMF() { // {maxflow, mincost}
    int retflow = 0, retcost = 0;
    while (1) {
        memset(par, -1, sizeof(par));
        memset(inque, 0, sizeof(inque));
        fill(stepcost, stepcost + NODE, INF);
        stepcost[source] = 0;

        queue<int> que;
        que.push(source);
        inque[source] = 1;

        while (!que.empty()) {
            int cur = que.front(); que.pop();
            inque[cur] = 0;
            for (auto& nxt : G[cur]) {
                if (edge[cur][nxt] > 0 && stepcost[cur] + cost[cur][nxt] < stepcost[nxt]) {
                    stepcost[nxt] = stepcost[cur] + cost[cur][nxt];
                    par[nxt] = cur;
                    if (!inque[nxt]) {
                        que.push(nxt);
                        inque[nxt] = 1;
                    }
                }
            }
        }

        if (par[sink] == -1) break;

        int flow = INF;
        for (int i = sink; i != source; i = par[i]) flow = min(flow, edge[par[i]][i]);
        for (int i = sink; i != source; i = par[i]) {
            retcost += cost[par[i]][i] * flow;
            edge[par[i]][i] -= flow;
            edge[i][par[i]] += flow;
        }
        retflow += flow;
    }

    return make_pair(retflow, retcost);
}

int N, M, H, T;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int n = 1; n <= N; n++) {
        G[n].emplace_back(n + 1000);
        G[n + 1000].emplace_back(n);
        edge[n][n + 1000] = 1;
    }
    while (M--) {
        int L, U, V; cin >> L >> U >> V;
        G[U + 1000].emplace_back(V);
        G[V].emplace_back(U + 1000);
        G[V + 1000].emplace_back(U);
        G[U].emplace_back(V + 1000);
        edge[U + 1000][V] = edge[V + 1000][U] = 1;
        cost[U + 1000][V] = cost[V + 1000][U] = L, cost[U][V + 1000] = cost[V][U + 1000] = -L;
    }
    cin >> H >> T;
    G[source].emplace_back(H + 1000);
    G[T].emplace_back(sink);
    edge[source][H + 1000] = edge[T][sink] = 2;

    auto p = MCMF();
    if (p.first < 2) cout << -1;
    else cout << p.second;
}