MinCostMaxFlow (PriorityQueue without objects)

class VertexPriorityQueue {
        long[] dist;
        int[] posInHeap;
        int[] heap;
        int heapSize;

        VertexPriorityQueue(int n) {
            dist = new long[n];
            Arrays.fill(dist, Long.MAX_VALUE);
            posInHeap = new int[n];
            Arrays.fill(posInHeap, -1);
            heap = new int[n];
            heapSize = 0;
        }

        void clear() {
            while (heapSize > 0) {
                removeFromHeap(heap[heapSize - 1]);
                heapSize--;
            }
        }

        void removeFromHeap(int vertex) {
            int pos = posInHeap[vertex];
            if (pos == -1) {
                return;
            }
            heapSize--;
            if (pos < heapSize) {
                swap(pos, heapSize);
                int lastPos = siftUp(pos);
                siftDown(lastPos);
            }
            dist[vertex] = Long.MAX_VALUE;
            posInHeap[vertex] = -1;
            if (heapSize < 0) {
                throw new AssertionError();
            }
        }

        void set(int vertex, int pos) {
            posInHeap[vertex] = pos;
            heap[pos] = vertex;
        }

        void swap(int p1, int p2) {
            int v1 = heap[p1];
            int v2 = heap[p2];
            set(v1, p2);
            set(v2, p1);
        }

        void siftDown(int pos) {
            while (pos > 0) {
                int parentPos = (pos - 1) >>> 1;
                if (dist[heap[parentPos]] <= dist[heap[pos]]) {
                    break;
                }
                swap(pos, parentPos);
                pos = parentPos;
            }
        }

        int siftUp(int pos) {
            while (true) {
                int ch1 = pos * 2 + 1, ch2 = pos * 2 + 2;
                if (ch1 >= heapSize) {
                    break;
                }
                int minChildPos = ch2 >= heapSize ? ch1 : (dist[heap[ch1]] < dist[heap[ch2]] ? ch1 : ch2);
                if (dist[heap[pos]] < dist[heap[minChildPos]]) {
                    break;
                }
                swap(pos, minChildPos);
                pos = minChildPos;
            }
            return pos;
        }

        void add(int vertex, long d) {
            if (d >= dist[vertex]) {
                throw new AssertionError();
            }
            removeFromHeap(vertex);
            dist[vertex] = d;
            set(vertex, heapSize++);
            siftDown(heapSize - 1);
        }

        int poll() {
            if (heapSize == 0) {
                throw new AssertionError();
            }
            int resVertex = heap[0];
            removeFromHeap(resVertex);
            return resVertex;
        }

        boolean isEmpty() {
            return heapSize == 0;
        }
    }

    class MinCostMaxFlowGraph {
        int n;
        int totEdges;
        int[] edgeFrom, edgeTo;
        long[] edgeCap, edgeFlow, edgeCost;
        int[] edgeRev;
        int[][] g;


        int newEdge(int from, int to, long cap, long flow, long cost) {
            edgeFrom[totEdges] = from;
            edgeTo[totEdges] = to;
            edgeCap[totEdges] = cap;
            edgeFlow[totEdges] = flow;
            edgeCost[totEdges] = cost;
            totEdges++;
            return totEdges - 1;
        }

        public MinCostMaxFlowGraph(int n, int maxEdges) {
            maxEdges *= 2;
            this.n = n;
            totEdges = 0;
            edgeFrom = new int[maxEdges];
            edgeTo = new int[maxEdges];
            edgeCap = new long[maxEdges];
            edgeFlow = new long[maxEdges];
            edgeCost = new long[maxEdges];
            edgeRev = new int[maxEdges];
        }

        public void addEdge(int fr, int to, int cap, long cost) {
            int e1 = newEdge(fr, to, cap, 0, cost);
            int e2 = newEdge(to, fr, 0, 0, -cost);
            edgeRev[e1] = e2;
            edgeRev[e2] = e1;
        }

        void buildAllEdges() {
            int[] edgesNum = new int[n];
            for (int eId = 0; eId < totEdges; eId++) {
                edgesNum[edgeFrom[eId]]++;
            }
            g = new int[n][];
            for (int i =0 ; i < n; i++) {
                g[i] = new int[edgesNum[i]];
            }
            for (int eId = 0; eId < totEdges; eId++) {
                g[edgeFrom[eId]][--edgesNum[edgeFrom[eId]]] = eId;
            }
        }

        public long[] getMinCostMaxFlow(int source, int target) {
            buildAllEdges();
            long[] h = new long[n];
            for (boolean changed = true; changed; ) {
                changed = false;
                for (int i = 0; i < n; i++) {
                    for (int eId : g[i]) {
                        if (edgeCap[eId] > 0 && h[edgeTo[eId]] > h[edgeFrom[eId]] + edgeCost[eId]) {
                            h[edgeTo[eId]] = h[edgeFrom[eId]] + edgeCost[eId];
                            changed = true;
                        }
                    }
                }
            }
            long[] d = new long[n];
            int[] prevEdge = new int[n];
            VertexPriorityQueue pq = new VertexPriorityQueue(d.length);
            int flow = 0;
            long cost = 0;
            while (true) {
                pq.clear();
                dijkstra(source, d, h, prevEdge, pq);
                if (d[target] == Long.MAX_VALUE) {
                    break;
                }
                long addFlow = Long.MAX_VALUE;
                int v = target;
                while (v != source) {
                    int e = prevEdge[v];
                    addFlow = Math.min(addFlow, edgeCap[e] - edgeFlow[e]);
                    v = edgeFrom[e];
                }
                cost += (d[target] + h[target] - h[source]) * addFlow;
                flow += addFlow;
                v = target;
                while (v != source) {
                    int e = prevEdge[v];
                    edgeFlow[e] += addFlow;
                    edgeFlow[edgeRev[e]] -= addFlow;
                    v = edgeFrom[e];
                }
                for (int i = 0; i < n; i++) {
                    h[i] += d[i] == Long.MAX_VALUE ? 0 : d[i];
                }
            }
            return new long[]{flow, cost};
        }

        void dijkstra(int source, long[] d, long[] h, int[] prevEdge, VertexPriorityQueue pq) {
            Arrays.fill(d, Long.MAX_VALUE);
            d[source] = 0;
            pq.add(source, 0);
            while (!pq.isEmpty()) {
                int v = pq.poll();
                for (int e : g[v]) {
                    if (edgeFlow[e] >= edgeCap[e]) {
                        continue;
                    }
                    if (d[edgeTo[e]] == Long.MAX_VALUE
                            || d[edgeTo[e]] > d[edgeFrom[e]] + edgeCost[e] + h[edgeFrom[e]]
                            - h[edgeTo[e]]) {
                        if (edgeCost[e] + h[edgeFrom[e]] - h[edgeTo[e]] < 0) {
                            throw new AssertionError();
                        }
                        d[edgeTo[e]] = d[edgeFrom[e]] + edgeCost[e] + h[edgeFrom[e]] - h[edgeTo[e]];
                        prevEdge[edgeTo[e]] = e;
                        pq.add(edgeTo[e], d[edgeTo[e]]);
                    }
                }
            }
        }
    }