[BOJ 3640] 제독

문제 출처 : https://www.acmicpc.net/problem/3640

 

풀이 :

MCMF 문제입니다.

1 을 source, V 를 sink로 잡고 mcmf를 해주시면 되는데

조건중에 정점 중복이 없다라는 말이 있으므로 정점 분할을 하고 

V번 정점에서 V ' 번 정점으로 가는 Capacity를 2로,

S번 정점에서 S ' 번 정점으로 가는 Capacity를 충분히 준 후 MCMF를 돌리시면 됩니다.

아래는 2번째 인풋을 모델링 한 그림입니다.

 

 

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define ms 2000
 
struct MCMF {
    struct edge {
        int to, c, f, w;
        edge *d;
        edge(int to1 = -1, int c1 = 0, int w1 = 0) :to(to1), c(c1), f(0), w(w1), d(nullptr) {}
        int spare() { return c - f; }
        void addFlow(int f1) {
            f += f1;
            d->f -= f1;
        }
    };
 
    int S = 0, E, mc, mf, v, e, a, b, c;
    vector<edge*>adj[ms];
 
    void init() {
        for (int i = 0; i < ms; i++) adj[i].clear();
        mf = mc = 0;
    }
 
    void addEdge(int u, int v, int c, int w) {
        edge *e1 = new edge(v, 1, w), *e2 = new edge(u, 0, -w);
        e1->d = e2;
        e2->d = e1;
        adj[u].push_back(e1);
        adj[v].push_back(e2);
    }
 
    int solve() {
        while (1) {
            int pre[ms];
            edge* path[ms] = { 0 };
            bool InQ[ms] = { 0 };
            int dist[ms] = { 0 };
            for (int i = 0; i < ms; i++) {
                pre[i] = -1;
                dist[i] = 1e9;
            }
            queue<int> q;
            q.push(S);
            dist[S] = 0;
            while (!q.empty()) {
                int now = q.front();
                q.pop();
                InQ[now] = false;
                for (edge *e : adj[now]) {
                    int next = e->to;
                    if (e->spare() > 0 && dist[next] > dist[now] + e->w) {
                        pre[next] = now;
                        path[next] = e;
                        dist[next] = dist[now] + e->w;
                        if (!InQ[next]) {
                            q.push(next);
                            InQ[next] = true;
                        }
                    }
                }
            }
            if (pre[E] == -1)break;
            for (int i = E; i != S; i = pre[i]) {
                path[i]->addFlow(1);
                mc += path[i]->w;
            }
            mf++;
        }
        return mc;
    }
 
    void inp() {
        while (cin >> v >> e) {
            init();
            for (int i = 0; i < v; i++) {
                int u = i * 2, v = u + 1;
                addEdge(u, v, 1, 0);
            }
            adj[(v - 1) * 2][0]->c = 2;
            adj[S][0]->c = e;
            E = (v - 1) * 2 + 1;
            while (e--) {
                cin >> a >> b >> c;
                a--;
                b--;
                addEdge(a * 2 + 1, b * 2, 1, c);
            }
            cout << solve() << '\n';
        }
    }
};
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    MCMF mcmf;
    mcmf.init();
    mcmf.inp();
}