3640 제독

같은 중간지점을 이용하지 않고 출발지 1에서 목적지 v까지 배 두대를 이용해서 움직일 때 소모값의 최소값을 구하는 문제다.

처음 풀었던 왕복여행 문제와 비슷하긴 하나 같은 중간지점을 이용하지 않는다는 점이 중요하다.

간선을 가지고 특정 중간지점을 두번 사용했는지 확인하기 위해 정점을 나눈다.

예제를 가지고 문제를 푼다고 하면 그림과 같이 1~n번 정점을 두개로 나누고, 출발지, 도착지를 제외한 나머지 정점의 내부 간선의 cap을 1로 둔다.

이렇게 하면 각 정점을 한번밖에 이용하지 못하게 된다. 출발지, 도착지의 내부간선의 cap은 2다.

정점을 쪼갤 때 번호지정은 편한대로 하면 된다.

<코드>

#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) {}
};
 
void aE(int u, int v, int c, int co, vector<vector<E *>> &g) {
    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, res, d[2010], INF = 2e9;
pii f[2010];
bool ch[2010];
 
int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        res = 0; k = 2 * n + 1;
        vector<vector<E *>> g(2 * n + 2);
        aE(1, 2, 2, 0, g);
        aE(2 * n - 1, 2 * n, 2, 0, g);
        for (int i = 4; i < g.size() - 2; i += 2) aE(i - 1, i, 1, 0, g);
        aE(s, 1, 2, 0, g);
        aE(2 * n, k, 2, 0, g);
        for (int i = 0; i < m; i++) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            a *= 2; b *= 2;
            aE(a, b - 1, 1, c, g);
        }
        while (1) {
            memset(f, -1, sizeof(f));
            memset(ch, false, sizeof(ch));
            fill(d, d + g.size(), INF);
            queue<int> q;
            q.push(s);
            d[s] = 0;
            while (q.size()) {
                int x = q.front();
                q.pop();
                ch[x] = 0;
                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;
            for (int x = k; 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;
}