2311 왕복 여행

처음 도전해본 MCMF문제.

편도 최소시간은 다익스트라로 하면 되지만 왕복 최소시간은 다익스트라*2가 통하지 않는 경우가 있다.

MCMF를 설명하기에는 아직 아는게 너무 부족하다. 연습 숙련이 답인듯.

<코드>

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
 
struct E {
    int t, c, co;
    E *rev;
    E(int t, int c, int co) : t(t), c(c), co(co) {}
};
 
vector<vector<E *>> g;
 
void aE(int u, int v, int c, int co) {
    E *ori = new E(v, c, co);
    E *rev = new E(u, 0, -co);
    ori->rev = rev;
    rev->rev = ori;
    g[u].push_back(ori);
    g[v].push_back(rev);
}
 
int n, m, s, k;
int d[1003], INF = 2e9;
pii f[1003];
bool ch[1003];
 
int main() {
    scanf("%d%d", &n, &m);
    k = n + 1;
    g.resize(n + 2);
    while (m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        aE(a, b, 1, c);
        aE(b, a, 1, c);
    }
    aE(s, 1, 2, 0);
    aE(n, k, 2, 0);
    int res = 0;
    while (1) {
        memset(f, -1, sizeof(f));
        memset(ch, false, sizeof(ch));
        fill(d, d + n + 2, INF);
        queue<int> q;
        d[s] = 0;
        q.push(s);
        while (q.size()) {
            int x = q.front();
            q.pop();
            ch[x] = false;
            for (int i = 0; i < g[x].size(); i++) {
                auto nx = g[x][i];
                if (nx->c > 0 && d[nx->t] > d[x] + nx->co) {
                    d[nx->t] = d[x] + nx->co;
                    f[nx->t] = { x,i };
                    if (!ch[nx->t]) {
                        ch[nx->t] = 1;
                        q.push(nx->t);
                    }
                }
            }
        }
        if (f[k].first == -1) break;
        int x = k;
        for (; x != s; x = f[x].first) {
            res += g[f[x].first][f[x].second]->co;
            g[f[x].first][f[x].second]->c -= 1;
            g[f[x].first][f[x].second]->rev->c += 1;
        }
    }
    printf("%d\n", res);
 
    return 0;
}