존슨 알고리즘 ( C++ , Java )

[두부장수 장홍준 3 - 14424](https://www.acmicpc.net/problem/14424\)

최대유량 최대비용 Code
최대유량 최소비용을 구하기 위해서는 MCMF() 함수에서 if (P < 0) 로 바꿔야함.

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

#define int int_fast64_t

using pii = pair<int, int>;
constexpr int INF = 1e9 + 7;

struct MCMF { //reference : https://justicehui.github.io/hard-algorithm/2020/03/24/effective-mcmf/
    struct Edge {
        int nxt;
        int inv; //inverse edge index
        int res; //residual
        int cost; //cost
    };

    vector<vector<Edge>> adj;
    vector<int> h, inq; //johnson's algorithm, spfa
    vector<int> dist; //dijkstra
    vector<int> check, work; //max flow
    int sz, s, e; //source, sink

    MCMF(int sz) :
            adj(sz), h(sz), inq(sz),
            dist(sz), check(sz), work(sz),
            sz(sz), s(-1), e(-1) {
    }

    void set_source(int t) { s = t; }
    void set_sink(int t) { e = t; }
    void add_edge(int a, int b, int fl, int cost) {
        Edge forward{ b, (int)adj[b].size(), fl, cost };
        Edge reverse({ a, (int)adj[a].size(), 0, -cost });
        adj[a].push_back(forward);
        adj[b].push_back(reverse);
    }
    void init() {
        fill(h.begin(), h.end(), INF);
        fill(dist.begin(), dist.end(), INF);

        //johnson's algorithm with spfa
        queue<int> Q;
        inq[s] = 1;
        Q.push(s);
        while (Q.size()) {
            int cur = Q.front(); Q.pop(); inq[cur] = 0;
            for (auto i : adj[cur]) {
                if (i.res && h[i.nxt] > h[cur] + i.cost) {
                    h[i.nxt] = h[cur] + i.cost;
                    if (!inq[i.nxt]) {
                        inq[i.nxt] = 1;
                        Q.push(i.nxt);
                    }
                }
            }
        }
        for (int i = 0; i < sz; i++) {
            for (auto& j : adj[i]) {
                if (j.res) j.cost += h[i] - h[j.nxt];
            }
        }

        //get shortest path DAG with dijkstra
        priority_queue<pii, vector<pii>, greater<pii>> PQ;
        dist[s] = 0;
        PQ.push({ dist[s], s });
        while (PQ.size()) {
            auto [cost, cur] = PQ.top();
            PQ.pop();
            if (dist[cur] ^ cost) continue;
            for (auto i : adj[cur]) {
                if (i.res && dist[i.nxt] > dist[cur] + i.cost) {
                    dist[i.nxt] = dist[cur] + i.cost;
                    PQ.push({ dist[i.nxt], i.nxt });
                }
            }
        }
        for (int i = 0; i < sz; i++) dist[i] += h[e] - h[s];
    }
    bool update() { //update shortest path DAG in O(V+E)
        int mn = INF;
        for (int i = 0; i < sz; i++) {
            if (!check[i]) continue;
            for (auto j : adj[i]) {
                if (j.res && !check[j.nxt]) mn = min(mn, dist[i] + j.cost - dist[j.nxt]);
            }
        }
        if (mn >= INF) return 0;
        for (int i = 0; i < sz; i++) {
            if (!check[i]) dist[i] += mn;
        }
        return 1;
    }
    int dfs(int cur, int fl) {
        check[cur] = 1;
        if (cur == e) return fl;
        for (; work[cur] < adj[cur].size(); work[cur]++) {
            auto& i = adj[cur][work[cur]];
            if (!check[i.nxt] && dist[i.nxt] == dist[cur] + i.cost && i.res) {
                int ret = dfs(i.nxt, min(fl, i.res));
                if (ret) {
                    i.res -= ret;
                    adj[i.nxt][i.inv].res += ret;
                    return ret;
                }
            }
        }
        return 0;
    }
    pii mcmf() { //cost, flow
        if (s == -1 || e == -1) return { -1, -1 };
        init();
        int cost = 0, fl = 0;
        do {
            fill(check.begin(), check.end(), 0);
            fill(work.begin(), work.end(), 0);
            int cur = 0;
            while (cur = dfs(s, INF)) {
                int P = dist[e] * cur;
                if (P>0) { break;} // 최소비용일땐 < 최대비용일땐 >
                cost += dist[e] * cur;
                fl += cur;
                fill(check.begin(), check.end(), 0);
            }
        } while (update());
        return { cost, fl };
    }
};

int get_cost(char a, char b){
    if(a > b)
        swap(a, b);
    if(a == 'A'){
        if(b == 'A')
            return 10;
        if(b == 'B')
            return 8;
        if(b == 'C')
            return 7;
        if(b == 'D')
            return 5;
        return 1;
    } else if(a == 'B'){
        if(b == 'B')
            return 6;
        if(b == 'C')
            return 4;
        if(b == 'D')
            return 3;
        return 1;
    } else if(a == 'C'){
        if(b == 'C')
            return 3;
        if(b == 'D')
            return 2;
        return 1;
    } else if (a == 'D'){
        if(b == 'D')
            return 2;
        return 1;
    }
    return 0;
}

int32_t main(){
    int cost[5][5]{
            { 10, 8, 7, 5, 1 },
            {  8, 6, 4, 3, 1 },
            {  7, 4, 3, 2, 1 },
            {  5, 3, 2, 2, 1 },
            {  1, 1, 1, 1, 0 },
    };

    int n, m; cin >> n >> m;
    vector<string> board(n);
    for (int i = 0; i < n; i++) {
        cin >> board[i];
        for (auto& i : board[i]) if (i == 'F') i = 'E';
    }
    int s = n * m, e = n * m + 1;
    MCMF mcmf(n * m + 2);
    mcmf.set_source(s);
    mcmf.set_sink(e);

    int dx[] =  {-1,1,0,0};
    int dy[] =  {0,0,-1,1};
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (i + j & 1) {
                mcmf.add_edge(s, i * m + j, 1, 0);
                mcmf.add_edge(i * m + j, e, 1, 0);
                for (int k = 0; k < 4; k++) {
                    int nx = i  + dx[k];
                    int ny = j + dy[k];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    mcmf.add_edge(i * m + j, nx * m + ny, 1, -cost[board[i][j] - 'A'][board[nx][ny] - 'A']);
                }
            }
            else mcmf.add_edge(i * m + j, e, 1, 0);
        }
    cout << -mcmf.mcmf().first << '\n';
}

import static java.lang.Integer.*;
import static java.lang.Integer.MAX_VALUE;

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N, M, length;

        N = parseInt(st.nextToken());
        M = parseInt(st.nextToken());
        length = N * M + 2;

        int[][] cost = {
            {10, 8, 7, 5, 1},
            {8, 6, 4, 3, 1},
            {7, 4, 3, 2, 1},
            {5, 3, 2, 2, 1},
            {1, 1, 1, 1, 0},
        };

        char[][] board = new char[N][M];
        int[][] number = new int[N][M];
        int count = 1;
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                if (line.charAt(j) == 'F') {
                    board[i][j] = 'E';
                } else {
                    board[i][j] = line.charAt(j);
                }
                number[i][j] = count++;
            }
        }
        MCMF mcmf = new MCMF(length);
        mcmf.setSource(0);
        mcmf.setSink(N * M + 1);
        int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

        for (int i = 0 ; i < N ; i++) {
            for (int j = 0 ; j < M ; j ++) {
                if ((i+j)%2==0) {
                    mcmf.addEdge(mcmf.source, number[i][j], 1, 0);
                    for (int k = 0 ; k < 4 ; k++) {
                        int nx = i+dx[k] , ny = j + dy[k];
                        if (nx<0 || nx>=N || ny<0 || ny>=M) continue;
                        mcmf.addEdge(number[i][j], number[nx][ny], 1,
                            -cost[(int) board[i][j] - (int) 'A'][(int) board[nx][ny] - (int) 'A']);
                    }
                } else {
                    mcmf.addEdge(number[i][j]  , mcmf.sink , 1 , 0);
                }
            }
        }

        bw.write(Integer.toString(-mcmf.MCMF()[0]));
        bw.flush();
        br.close();
        bw.close();
    }
}

class MCMF {

    static class Edge {

        int node, rev, res, cost;

        // 현재노드 , 이전노드 , 용량-유량 , 비용
        Edge(int node, int rev, int res, int cost) {
            this.node = node;
            this.rev = rev;
            this.res = res;
            this.cost = cost;
        }
    }


    ArrayList<Edge>[] graph;
    int[] h, inq;
    int[] distance;
    int[] check, work;

    int size, source, sink;

    MCMF(int size) {
        this.size = size;
        this.graph = new ArrayList[size];
        this.h = new int[size];
        this.inq = new int[size];
        this.distance = new int[size];
        this.check = new int[size];
        this.work = new int[size];

        for (int i = 0 ; i < size ; i++) this.graph[i] = new ArrayList<>();
    }

    void setSource(int source) {
        this.source = source;
    }

    void setSink(int sink) {
        this.sink = sink;
    }

    void addEdge(int u, int v, int capacity, int cost) {
        Edge e1 = new Edge(v, graph[v].size(), capacity, cost);
        Edge e2 = new Edge(u, graph[u].size(), 0, -cost);
        graph[u].add(e1);
        graph[v].add(e2);
    }

    void init() {
        Arrays.fill(h, MAX_VALUE);
        Queue<Integer> Q = new LinkedList<>();
        inq[source] = 1;
        Q.add(source);

        while (!Q.isEmpty()) {
            int node = Q.poll();
            inq[node] = 0;
            for (Edge edge : graph[node]) {
                if (edge.res > 0 && h[edge.node] > h[node] + edge.cost) {
                    h[edge.node] = h[node] + edge.cost;
                    if (inq[edge.node] == 0) {
                        inq[edge.node] = 1;
                        Q.add(edge.node);
                    }
                }
            }
        }

        for (int i = 0; i < size; i++) {
            for (int j = 0; j < graph[i].size() ; j++) {
                if (graph[i].get(j).res > 0) {
                    graph[i].get(j).cost += h[i] - h[graph[i].get(j).node];
                    /** 존슨 알고리즘
                     *  h[u] + w(u,v) >= h[v];
                     *  h[u] + w(u,v) - h[v] >= 0;
                     */
                }
            }
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        Arrays.fill(distance, MAX_VALUE);
        distance[source] = 0;
        pq.add(new int[]{0, source});

        while (!pq.isEmpty()) {
            int cost = pq.peek()[0];
            int node = pq.peek()[1];
            pq.poll();

            if (distance[node] < cost) {
                continue;
            }

            for (Edge edge : graph[node]) {
                if (edge.res > 0 && distance[edge.node] > distance[node] + edge.cost) {
                    distance[edge.node] = distance[node] + edge.cost;
                    pq.add(new int[]{distance[edge.node], edge.node});
                }
            }
        }

        for (int i = 0; i < size; i++) {
            distance[i] += h[sink] - h[source];
        }
    }

    int dfs(int node, int networkFlow) {
        check[node] = 1;
        if (node == sink) {
            return networkFlow;
        }

        for (; work[node] < graph[node].size(); work[node]++) {
            Edge edge = graph[node].get(work[node]);
            if (check[edge.node] == 0 && distance[edge.node] == distance[node] + edge.cost
                && edge.res > 0) {
                int ret = dfs(edge.node, Math.min(networkFlow, edge.res));
                if (ret > 0) {
                    graph[node].get(work[node]).res -= ret;
                    graph[edge.node].get(edge.rev).res += ret;
                    return ret;
                }
            }
        }
        return 0;
    }

    boolean update() {
        int value = MAX_VALUE;
        for (int i = 0; i < size; i++) {
            if (check[i] == 0) {
                continue;
            }
            for (Edge edge : graph[i]) {
                if (edge.res > 0 && check[edge.node] == 0) {
                    value = Math.min(value, distance[i] + edge.cost - distance[edge.node]);
                }
            }
        }

        if (value == MAX_VALUE) {
            return false;
        }
        for (int i = 0; i < size; i++) {
            if (check[i] == 0) {
                distance[i] += value;
            }
        }
        return true;
    }

    int[] MCMF() {
        init();
        int cost = 0, flow = 0;
        do {
            Arrays.fill(check, 0);
            Arrays.fill(work, 0);
            int cur=0;
            while ((cur = dfs(source, MAX_VALUE)) != 0) {
                int P = distance[sink] * cur;
                if (P > 0) {  //최소비용일땐 < 최대비용일땐 >
                    break;
                }
                cost += distance[sink] * cur;
                flow += cur;
                Arrays.fill(check, 0);
            }
        } while (update());
        return new int[]{cost, flow};
    }
}