hckim

문제링크

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

풀이

• 시작점에서 끝지점까지 최대 용량을 2로 해두고 MCMF 해주기
• 두 경로사이에 겹치는 정점, 간선 없게하기위해 각 정점 한번씩만 지날 수 있도록 -> 정점분할
  • v : 2v - 1 -> 2v

코드

• 시간복잡도: $O((V+E)f) = O(V+E)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

struct Edge {
    int to, c, f, cost;
    Edge* reverse;

    Edge() {
        to = c = f = cost = 0;
        reverse = nullptr;
    }
    Edge(int to_, int c_, int cost_) {
        to = to_;
        c = c_;
        cost = cost_;
        f = 0;

        reverse = nullptr;
    }

    int reisidual() {
        return c - f;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int v, e;
    while (cin >> v >> e) {
        int S = 1;
        int T = 2 * v - 1;
        vector<vector<Edge*> > adj(2 * v + 1);

        auto makeEdge = [&](int u, int v, int c, int cost) {
            auto e1 = new Edge(v, c, cost);
            auto e2 = new Edge(u, 0, -cost);
            e1 -> reverse = e2;
            e2 -> reverse = e1;
            adj[u].push_back(e1);
            adj[v].push_back(e2);
        };

        while (e--) {
            int u, v, c;
            cin >> u >> v >> c;
            makeEdge(2 * u, 2 * v - 1, 1, c);
        }
        makeEdge(1, 2, 2, 0);
        for (int i = 2; i <= v; ++i) {
            makeEdge(2 * i - 1, 2 * i, 1, 0);
        }

        int maxFlow = 0;
        int minCost2 = 0;
        while (true) {
            vector<Edge*> prev(2 * v + 1, nullptr);
            queue<int> q;
            vector<int> inQ(2 * v + 1, false);
            vector<int> minCost(2 * v + 1, 1e9);
            q.push(S);
            minCost[S] = 0;
            inQ[S] = true;
            while (q.size()) {
                int cur = q.front();
                q.pop();
                inQ[cur] = false;
                for (auto e: adj[cur]) {
                    if (e -> reisidual() > 0 && minCost[e -> to] > minCost[cur] + e -> cost) {
                        minCost[e -> to] = minCost[cur] + e -> cost;
                        prev[e -> to] = e;
                        if (!inQ[e -> to]) {
                            q.push(e -> to);
                            inQ[e -> to] = true;
                        }
                    }
                }
            }

            if (!prev[T]) break;

            int flow = 1e9;
            for (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
                flow = min(flow, prev[cur] -> reisidual());
            }

            for (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
                prev[cur] -> f += flow;
                prev[cur] -> reverse -> f -= flow;
            }
            maxFlow += flow;
            minCost2 += minCost[T];
        }
        cout << minCost2 << '\n';
    }
}

문제링크

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

풀이

• K, H 를 두 부분으로 나누는 Minimum cut 구하기 = Maximum flow
• K, H 가 인접해서 있는 경우 불가능
• 벽으로 바꿀 칸은 한번만 flow 경로에 포함되어야 하므로 정점분할

코드

• 각 칸 정점번호: row * M + col
• 정점번호 u 의
  • in = 2 * u
  • out = 2 * u + 1

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

struct Edge {
    int to, c, f;
    Edge* reverse;
    Edge(int to_, int c_) {
        to = to_;
        c = c_;
        f = 0;
        reverse = nullptr;
    }

    int residual() {
        return c - f;
    }
};

int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;
    vector<string> a(N);
    for (auto& e: a) {
        cin >> e;
    }

    vector<vector<Edge*> > adj(2 * N * M);
    auto makeEdge = [&](int u, int v) {
        auto e1 = new Edge(v, 1);
        auto e2 = new Edge(u, 0);
        e1 -> reverse = e2;
        e2 -> reverse = e1;
        adj[u].push_back(e1);
        adj[v].push_back(e2);
    };

    int S, T;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (a[i][j] == '#') continue;

            if (a[i][j] == 'K') {
                S = 2 * (i * M + j) + 1;
            } else if (a[i][j] == 'H') {
                T = 2 * (i * M + j);
            }

            for (int dir = 0; dir < 4; ++dir) {
                int ni = i + dr[dir];
                int nj = j + dc[dir];
                if (ni < 0 || ni >= N || nj < 0 || nj >= M) continue;
                if (a[ni][nj] == '#') continue;
                makeEdge(2 * (i * M + j) + 1, 2 * (ni * M + nj));
            }
        }
    }
    for (int i = 0; i < N * M; ++i) {
        makeEdge(2 * i, 2 * i + 1);
    }

    if (abs(S / 2 / M - T / 2 / M) + abs(S / 2 % M - T / 2 % M) == 1) {
        cout << "-1\n";
        return 0;
    }

    int answer = 0;
    while (true) {
        vector<Edge*> prev(2 * N * M, nullptr);
        queue<int> q;
        q.push(S);

        while (q.size()) {
            auto f = q.front();
            q.pop();
            for (auto e: adj[f]) {
                if (prev[e -> to]) continue;
                if (e -> residual() <= 0) continue;

                prev[e -> to] = e;
                q.push(e -> to);
            }
        }

        if (!prev[T]) break;

        int flow = 1;
        answer += flow;
        for (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
            prev[cur] -> f += flow;
            prev[cur] -> reverse -> f -= flow;
        }
    }
    
    cout << answer << '\n';
}

문제링크

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

풀이

• 최대 유량문제에서 증가경로를 찾을 때 cost 에 대해 최단 경로로 찾음
• 역방향 간선의 cost 가 음수이므로 음수간선에 대해서도 동작해야함
  • SPFA

코드

• 시간복잡도: $O(VEf)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

struct Edge {
    int to, c, f, cost;
    Edge* reverse;

    Edge() {
        to = c = f = cost = 0;
        reverse = nullptr;
    }
    Edge(int to_, int c_, int cost_) {
        to = to_;
        c = c_;
        cost = cost_;
        f = 0;

        reverse = nullptr;
    }

    int reisidual() {
        return c - f;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    vector<int> A(N + 1, 0), B(M + 1, 0);
    vector<vector<Edge*> > adj(N + M + 2);
    int S = 0;
    int T = adj.size() - 1;
    auto makeEdge = [&](int u, int v, int c, int cost) {
        auto e1 = new Edge(v, c, cost);
        auto e2 = new Edge(u, 0, -cost);
        e1 -> reverse = e2;
        e2 -> reverse = e1;
        adj[u].push_back(e1);
        adj[v].push_back(e2);
    };
    
    for (int i = 1; i <= N; ++i) {
        makeEdge(S, i, 1, 0);
        int cnt = 0;
        cin >> cnt;
        while (cnt--) {
            int v, cost;
            cin >> v >> cost;
            makeEdge(i, N + v, 1, cost);
        }
    }
    for (int i = 1; i <= M; ++i) {
        makeEdge(N + i, T, 1, 0);
    }
    
    int maxFlow = 0;
    int minCost2 = 0;
    while (true) {
        vector<Edge*> prev(N + M + 2, nullptr);
        queue<int> q;
        vector<int> inQ(N + M + 2, false);
        vector<int> minCost(N + M + 2, 1e9);
        q.push(S);
        minCost[S] = 0;
        inQ[S] = true;
        while (q.size()) {
            int cur = q.front();
            q.pop();
            inQ[cur] = false;
            for (auto e: adj[cur]) {
                if (e -> reisidual() > 0 && minCost[e -> to] > minCost[cur] + e -> cost) {
                    minCost[e -> to] = minCost[cur] + e -> cost;
                    prev[e -> to] = e;
                    if (!inQ[e -> to]) {
                        q.push(e -> to);
                        inQ[e -> to] = true;
                    }
                }
            }
        }

        if (!prev[T]) break;
        
        int flow = 1e9;
        for (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
            flow = min(flow, prev[cur] -> reisidual());
        }

        for (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
            prev[cur] -> f += flow;
            prev[cur] -> reverse -> f -= flow;
        }
        maxFlow += flow;
        minCost2 += minCost[T];
    }

    cout << maxFlow << '\n';
    cout << minCost2 << '\n';
}

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

풀이

• 1, 2번 제외한 정점들은 한번씩만 지날 수 있다 -> 용량 1 인 간선으로 각 정점분할
  • u 의 in 정점 : 2u - 1, out 정점: 2u
  • in -> out 단방향 간선 용량 1
  • 1, 2번 정점은 여러번 지날 수 있어야 하므로 (in -> out) 간선 용량은 400(최대 경로 수) 로 지정
• u - v : 양방향 간선을 두개의 단방향 간선으로 (u out -> v in, v out -> u in)

코드

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

struct Edge {
    int to, c, f;
    Edge* reverse;
    Edge() {
        to = c = f = 0;
        reverse = nullptr; 
    }
    Edge(int to_, int c_) {
        f = 0;
        c = c_;
        to = to_;
        reverse = nullptr;
    }

    int residual() {
        return c - f;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, P;
    cin >> N >> P;

    vector<vector<Edge*> > adj(2 * N + 1);

    auto makeEdge = [&](int u, int v, int c) {
        auto e1 = new Edge(v, c);
        auto e2 = new Edge(u, 0);
        e1 -> reverse = e2;
        e2 -> reverse = e1;
        adj[u].push_back(e1);
        adj[v].push_back(e2);
    };

    for (int i = 0; i < P; ++i) {
        int u, v;
        cin >> u >> v;
        makeEdge(2 * u, 2 * v - 1, 1);
        makeEdge(2 * v, 2 * u - 1, 1);
    }
    for (int i = 1; i <= N; ++i) {
        int c = 1;
        if (i == 1 || i == 2) c = 400;
        makeEdge(2 * i - 1, 2 * i, c);
    }

    int S = 1 * 2 - 1;
    int T = 2 * 2;
    int answer = 0;

    while (true) {
        vector<Edge*> prev(2 * N + 1, nullptr);
        queue<int> q;
        q.push(S);
        while (q.size()) {
            auto f = q.front();
            q.pop();
            for (auto e: adj[f]) {
                if (prev[e -> to]) continue;
                if (e -> residual() <= 0) continue;
                q.push(e -> to);
                prev[e -> to] = e;
                if (e -> to == T) break;
            }
            if (prev[T]) break;
        }

        if (!prev[T]) break;

        int flow = 1e9;
        for (int cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
            flow = min(flow, prev[cur] -> residual());
        }

        for (int cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
            prev[cur] -> f += flow;
            prev[cur] -> reverse -> f -= flow;
        }
        answer += flow;
    }
    cout << answer << '\n';
}

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

풀이1. Maximum flow(에드몬드 카프)

최대 K 명까지 일을 두개 할 수 있다는 것을 Source 에서 용량 K 로 이어진 추가 노드를 구성함으로써 구현

코드1.

• 단방향 플로우에서 역방향 간선의 capacity = 0 으로 해야함에 주의
• 시간복잡도: $min(O((V + E)f), O(VE^2)) \to O((V + E)(V + K))$ 

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
struct Edge {
    int to, c, f;
    Edge* reverse;

    Edge() {
        to = 0;
        c = 0;
        f = 0;
        reverse = nullptr;
    }
    int residual() {
        return c - f;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<Edge*> > adj(N + M + 3);
    auto makeEdge = [&](int n1, int n2, int cc) {
        auto e1 = new Edge();
        auto e2 = new Edge();

        e1 -> to = n2;
        e1 -> reverse = e2;
        e1 -> c = cc;
        e2 -> to = n1;
        e2 -> reverse = e1;

        adj[n1].push_back(e1);
        adj[n2].push_back(e2);
    };

    int S = 0, T = N + M + 1, X = N + M + 2;

    makeEdge(S, X, K);
    for (int i = 1; i <= N; ++i) {
        int num;
        cin >> num;
        makeEdge(S, i, 1);
        makeEdge(X, i, 1);
        while (num--) {
            int w;
            cin >> w;
            makeEdge(i, N + w, 1);
        }
    }
    for (int i = 1; i <= M; ++i) {
        makeEdge(N + i, T, 1);
    }

    while (true) {
        vector<Edge*> prev(N + M + 3, nullptr);
        queue<int> q;
        q.push(S);
        while (!q.empty()) {
            auto f = q.front();
            q.pop();

            for (auto e: adj[f]) {
                if (e -> residual() <= 0) continue;
                if (prev[e -> to]) continue;
                q.push(e -> to);
                prev[e -> to] = e;
                if (e -> to == T) break;
            }
            if (prev[T]) break;
        }

        if (!prev[T]) break;

        int flow = 1e9;
        for (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
            flow = min(flow, prev[cur] -> residual());
        }
        for (auto cur = T; cur != S; cur = prev[cur] -> reverse -> to) {
            prev[cur] -> f += flow;
            prev[cur] -> reverse -> f -= flow;
        }
    }

    int answer = 0;
    for (auto e: adj[T]) {
        answer += e -> reverse -> f;
    }
    cout << answer << '\n';
}

풀이2. Bipartite matching

직원당 두개의 노드를 만들고 그룹 두개로 나눠서 한그룹에서 이분매칭 후 두번째 그룹에서 K번 이하 이분매칭

코드2. 

• 시간복잡도: $O(VE)$

#include <bits/stdc++.h>

using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, K;
    cin >> N >> M >> K;

    vector<int> A(2 * N + 1, 0), B(M + 1, 0);
    vector<vector<int> > adj(2 * N + 1);

    for (int i = 1; i <= N; ++i) {
        int num;
        cin >> num;
        while (num--) {
            int m;
            cin >> m;
            adj[2 * i - 1].push_back(m);
            adj[2 * i].push_back(m);
        }
    }

    vector<int> visited(2 * N + 1, false);
    function<bool(int)> f = [&](int a) {
        visited[a] = true;
        for (auto b: adj[a]) {
            if (!B[b] || (!visited[B[b]] && f(B[b]))) {
                A[a] = b;
                B[b] = a;
                return true;
            }            
        }
        return false;
    };

    int match = 0;
    for (int i = 1; i <= 2 * N; i += 2) {
        if (!A[i]) {
            fill(all(visited), false);
            if (f(i)) ++match;
        }
    }
    int matched2 = 0;
    for (int i = 2; i <= 2 * N && matched2 < K; i += 2) {
        if (!A[i]) {
            fill(all(visited), false);
            if (f(i)) ++matched2;
        }
    }

    cout << match + matched2 << '\n';
}