BOJ 3640 - 제독

boj-3640.cpp

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

typedef long long lld;
typedef pair<int, int> ii;

const int INF = 0x3f3f3f3f;
const lld LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;

struct edge {
    int next, flow, cap, d;
    edge* rev;
    edge(int next, int cap, int d = 0) : next(next), flow(0), cap(cap), rev(0), d(d) {}
    void add(int f) {
        flow += f;
        rev->flow -= f;
    }
    int sparse() {
        return cap - flow;
    }
};

#define MAX_V 2050

vector<edge*> adj[MAX_V];

// (cost, flow)
pair<lld, int> mcmf(int src, int sink) {
    lld cost = 0;
    int mf = 0;
    int prv[MAX_V];
    edge* pth[MAX_V];
    bool inQ[MAX_V];
    int dist[MAX_V];
    while (true) {
        memset(prv, -1, sizeof(prv));
        memset(pth, 0, sizeof(pth));
        memset(inQ, 0, sizeof(inQ));
        memset(dist, 0x3f, sizeof(dist));
        queue<int> q;
        q.push(src);
        dist[src] = 0;
        // spfa
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            inQ[cur] = false;
            for (auto& e : adj[cur]) {
                int nxt = e->next;
                if (e->sparse() > 0 && dist[nxt] > dist[cur] + e->d) {
                    dist[nxt] = dist[cur] + e->d;
                    prv[nxt] = cur;
                    pth[nxt] = e;
                    if (inQ[nxt]) continue;
                    q.push(nxt);
                    inQ[nxt] = true;
                }
            }
        }

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

        int flow = INF;
        for (int i = sink; i != src; i = prv[i])
            flow = min(flow, pth[i]->sparse());
        for (int i = sink; i != src; i = prv[i]) {
            cost += (lld)flow * pth[i]->d;
            pth[i]->add(flow);
        }
        mf += flow;
    }
    return { cost, mf };
}

void add_flow(int u, int v, int cap, int dist) {
    edge* p = new edge(v, cap, dist);
    edge* q = new edge(u, 0, -dist);
    p->rev = q;
    q->rev = p;
    adj[u].push_back(p);
    adj[v].push_back(q);
}

const int src = MAX_V - 1, sink = MAX_V - 2;

int main() {
    int v, e;
    while (~scanf("%d %d", &v, &e)) {
        adj[src].clear();
        adj[sink].clear();
        for (int i = 1; i <= 2 * v; ++i) adj[i].clear();

        add_flow(src, 1, 2, 0);
        add_flow(v + v, sink, 2, 0);
        for (int i = 1; i <= v; ++i) {
            int cap = i == 1 || i == v ? 2 : 1;
            add_flow(i, i + v, cap, 0);
        }

        while (e--) {
            int a, b, w;
            scanf("%d %d %d", &a, &b, &w);
            add_flow(a + v, b, 1, w);
        }

        auto ans = mcmf(src, sink);
        printf("%lld\n", ans.first);
    }
    return 0;
}