Min-Cost Max-Flow Solution (With Diagrams)
Intuition\n Matching problems can often be modeled into a flow network in which the min-cost max-flow represents the optimal solution.\n The key challenge here 
# Intuition\n* Matching problems can often be modeled into a flow network in which the min-cost max-flow represents the optimal solution.\n* The key challenge here is figuring out how to transform the input grid into such a network that respects the contstraints of the problem (i.e. uniqueness and the "1 selection per row" limit).\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nConsider example 1: \n![image.png](https://assets.leetcode.com/users/images/98fa22b5-2c2a-4dd2-9f9b-33f70e302b68_1725166484.0684252.png)\n\nThis example can be turned into the following flow network. \n\nNote:\n* The edges are labeled with cost/capacity. e.g. A "0/1" edge denotes to a cost of zero & capacity one edge.\n* We connect the source to each row, only giving it a capacity of 1. This is to enforce that each row only gets picked once.\n* We connect each row with the values found in that row, again, using a capacity of 1 to ensure we only pick once per row. \n* We then connect each unique value (the second column of nodes) to the sink with a capacity of 1 to ensure uniqueness. \n* Most of the costs are zero. The only costs occur when a row "selects" a specific value. The cost is `100 - x`.\n \n![image.png](https://assets.leetcode.com/users/images/72a6d6fc-470d-4db1-98a1-3ee7839c8141_1725166434.7422009.png)\n\nThe maximum flow of this flow \n\n\n\n is `3`. The minimum cost to achieve that flow is `96 + 97 + 99 = 292` (see the red edges below). \n\nIn order to convert this back into the max value that we\'re trying optimize for, we need to take `100 * max_flow` and subtract `292` (`100*3 - 292 = 8`). Hence, `8` is the maximum valid answer for example 1. \n\n![image.png](https://assets.leetcode.com/users/images/05c3c3dc-40ac-4f4c-88b3-2aa31de3ceea_1725167375.4760976.png)\n\n\nYou can solve the min-cost max-flow problem using a variety of algorithms, such as the Ford-Fulkerson, Edmonds-Karp, or the Dijkstra-based Min-Cost Max-Flow algorithm I\'ve used below. The exact specifics of how such algorithms work are out of scope for this tutorial. \n\n\n**Bonus**: If you\'re curious, here\'s how the flow network would look like for example 2.\n![image.png](https://assets.leetcode.com/users/images/b9327bf4-a002-4f0b-b447-6cd65f683c9e_1725456264.1705003.png)\n\n\n![image.png](https://assets.leetcode.com/users/images/14c5886d-852b-4081-bff6-471d527c2e70_1725456313.6583967.png)\n\nNote that node \'8\' cannot take in more than one flow, hence row0 gets rerouted to node \'7\'. Here the max-flow is `2` and the min-cost is `92 + 93 = 185`\n\n# Complexity\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Time complexity: `O( max_flow * n * m * log(n + m) )`\nNote: n & m are the dimensions of the grid, and the max_flow will be less than or equal to n. Hence the overall algorithm runs in: `O( n^2 * m * log(n + m) )`\n\n- Space complexity: `O(n+m)`\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n\nStructure:\n* Build flow network, with inverted cost values per cell (`100-x`)\n* Invoke the min-cost max-flow helper function\n* Return: `100 * max_flow - min_cost`\n\n```java []\nclass Solution {\n    public int maxScore(List<List<Integer>> grid) {\n        int n = grid.size(); // first column of nodes\n        int m = 100; // second column of nodes\n        int size = n + m + 2;\n        var f = new DijkstraMinCostMaxFlow(size);\n\n        for (int i = 1; i <= n; i++) { // connect the source to first column\n            f.addEdge(0, i, 1, 0);\n        }\n\n        for (int i = 0; i < n; i++) { // interconnections between columns\n            for (int j : grid.get(i)) {\n                f.addEdge(i + 1, j + n, 1, 100 - j);\n            }\n        }\n\n        for (int i = 1; i <= 100; i++) { // connect the second column to the sink\n            f.addEdge(i + n, size - 1, 1, 0);\n        }\n\n        int[] mf = f.minCostMaxFlow(0, size - 1);\n        return 100 * mf[0] - mf[1]; // needed to convert back, sum(100-x) --> sum(x)\n    }\n}\n\npublic class DijkstraMinCostMaxFlow {\n\n    static class Edge {\n        int from, to, capacity, cost, flow;\n        Edge reverse;\n\n        public Edge(int from, int to, int capacity, int cost) {\n            this.from = from;\n            this.to = to;\n            this.capacity = capacity;\n            this.cost = cost;\n            this.flow = 0;\n        }\n    }\n\n    private int n;\n    private List<Edge>[] graph;\n    private int[] potential;\n\n    public DijkstraMinCostMaxFlow(int n) {\n        this.n = n;\n        graph = new ArrayList[n];\n        for (int i = 0; i < n; i++) {\n            graph[i] = new ArrayList<>();\n        }\n        potential = new int[n];\n    }\n\n    public void addEdge(int from, int to, int capacity, int cost) {\n        Edge forward = new Edge(from, to, capacity, cost);\n        Edge reverse = new Edge(to, from, 0, -cost);\n        forward.reverse = reverse;\n        reverse.reverse = forward;\n        graph[from].add(forward);\n        graph[to].add(reverse);\n    }\n\n    private boolean dijkstra(int source, int sink, int[] dist, Edge[] parentEdge) {\n        Arrays.fill(dist, Integer.MAX_VALUE);\n        dist[source] = 0;\n        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));\n        pq.add(new int[] { source, 0 });\n\n        while (!pq.isEmpty()) {\n            int[] u = pq.poll();\n            int current = u[0];\n            int currentDist = u[1];\n\n            if (currentDist > dist[current])\n                continue;\n\n            for (Edge edge : graph[current]) {\n                int next = edge.to;\n                int newDist = dist[current] + edge.cost + potential[current] - potential[next];\n\n                if (edge.flow < edge.capacity && dist[next] > newDist) {\n                    dist[next] = newDist;\n                    parentEdge[next] = edge;\n                    pq.add(new int[] { next, dist[next] });\n                }\n            }\n        }\n\n        for (int i = 0; i < n; i++) {\n            if (dist[i] < Integer.MAX_VALUE) {\n                potential[i] += dist[i];\n            }\n        }\n\n        return dist[sink] != Integer.MAX_VALUE;\n    }\n\n    public int[] minCostMaxFlow(int source, int sink) {\n        int maxFlow = 0, minCost = 0;\n        int[] dist = new int[n];\n        Edge[] parentEdge = new Edge[n];\n\n        Arrays.fill(potential, 0);\n\n        while (dijkstra(source, sink, dist, parentEdge)) {\n            int flow = Integer.MAX_VALUE;\n            for (int v = sink; v != source; v = parentEdge[v].from) {\n                flow = Math.min(flow, parentEdge[v].capacity - parentEdge[v].flow);\n            }\n\n            for (int v = sink; v != source; v = parentEdge[v].from) {\n                parentEdge[v].flow += flow;\n                parentEdge[v].reverse.flow -= flow;\n                minCost += flow * parentEdge[v].cost;\n            }\n\n            maxFlow += flow;\n        }\n\n        return new int[] { maxFlow, minCost };\n    }\n}\n```
['Graph', 'Java']