Submission #1148121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148121		rebe__1	Coin Collecting (JOI19_ho_t4)	Java	37 / 100	1103 ms	232612 KiB

joi2019_ho_t4

import java.util.*;

public class joi2019_ho_t4 {

    static class Edge {
        int to, rev, cap, cost;
        public Edge(int to, int rev, int cap, int cost) {
            this.to = to;
            this.rev = rev;
            this.cap = cap;
            this.cost = cost;
        }
    }

    static final int INF = Integer.MAX_VALUE / 2;

    static class MinCostFlow {
        int N;
        ArrayList<Edge>[] graph;
        int[] dist, potential, prevV, prevE;

        @SuppressWarnings("unchecked")
        public MinCostFlow(int N) {
            this.N = N;
            graph = new ArrayList[N];
            for (int i = 0; i < N; i++) {
                graph[i] = new ArrayList<>();
            }
            dist = new int[N];
            potential = new int[N];
            prevV = new int[N];
            prevE = new int[N];
        }

        public void addEdge(int s, int t, int cap, int cost) {
            graph[s].add(new Edge(t, graph[t].size(), cap, cost));
            graph[t].add(new Edge(s, graph[s].size() - 1, 0, -cost));
        }

        public int minCostFlow(int s, int t, int f) {
            int res = 0;
            Arrays.fill(potential, 0);

            while (f > 0) {
                PriorityQueue<Pair> pq = new PriorityQueue<>();
                Arrays.fill(dist, INF);
                dist[s] = 0;
                pq.add(new Pair(s, 0));

                while (!pq.isEmpty()) {
                    Pair p = pq.poll();
                    int v = p.v;
                    if (dist[v] < p.dist) continue;
                    for (int i = 0; i < graph[v].size(); i++) {
                        Edge e = graph[v].get(i);
                        if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + potential[v] - potential[e.to]) {
                            dist[e.to] = dist[v] + e.cost + potential[v] - potential[e.to];
                            prevV[e.to] = v;
                            prevE[e.to] = i;
                            pq.add(new Pair(e.to, dist[e.to]));
                        }
                    }
                }

                if (dist[t] == INF) {
                    return -1;
                }

                for (int v = 0; v < N; v++) {
                    if (dist[v] < INF)
                        potential[v] += dist[v];
                }

                int addFlow = f;
                for (int v = t; v != s; v = prevV[v]) {
                    addFlow = Math.min(addFlow, graph[prevV[v]].get(prevE[v]).cap);
                }
                f -= addFlow;
                res += addFlow * potential[t];

                for (int v = t; v != s; v = prevV[v]) {
                    Edge e = graph[prevV[v]].get(prevE[v]);
                    e.cap -= addFlow;
                    graph[v].get(e.rev).cap += addFlow;
                }
            }
            return res;
        }
    }

    static class Pair implements Comparable<Pair> {
        int v, dist;
        public Pair(int v, int dist) {
            this.v = v;
            this.dist = dist;
        }
        public int compareTo(Pair other) {
            return Integer.compare(this.dist, other.dist);
        }
    }

    private static int constrain(int value, int min, int max) {
        return Math.max(min, Math.min(max, value));
    }

    private static long calculateMovesToBoundary(int col, int row, int numColumns) {
        long moves = 0;
        if (row < 1) moves += (1 - row);
        if (row > 2) moves += (row - 2);
        if (col < 1) moves += (1 - col);
        if (col > numColumns) moves += (col - numColumns);
        return moves;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numColumns = sc.nextInt();
        int totalCoins = 2 * numColumns;
        int[][] grid = new int[3][numColumns + 1];
        long boundaryCost = 0;

        for (int i = 0; i < totalCoins; i++) {
            int col = sc.nextInt();
            int row = sc.nextInt();
            boundaryCost += calculateMovesToBoundary(col, row, numColumns);
            int validCol = constrain(col, 1, numColumns);
            int validRow = constrain(row, 1, 2);
            grid[validRow][validCol]++;
        }

        int nodes = 2 * numColumns;
        int[] supply = new int[nodes];
        for (int c = 1; c <= numColumns; c++) {
            for (int r = 1; r <= 2; r++) {
                int idx = (c - 1) * 2 + (r - 1);
                supply[idx] = grid[r][c] - 1;
            }
        }

        int s = nodes;
        int t = nodes + 1;
        int totalNodes = nodes + 2;
        MinCostFlow mcf = new MinCostFlow(totalNodes);

        for (int c = 1; c < numColumns; c++) {
            for (int r = 1; r <= 2; r++) {
                int u = (c - 1) * 2 + (r - 1);
                int v = (c) * 2 + (r - 1);
                mcf.addEdge(u, v, INF, 1);
                mcf.addEdge(v, u, INF, 1);
            }
        }

        for (int c = 1; c <= numColumns; c++) {
            int u = (c - 1) * 2 + 0;
            int v = (c - 1) * 2 + 1;
            mcf.addEdge(u, v, INF, 1);
            mcf.addEdge(v, u, INF, 1);
        }

        int totalPositive = 0;
        for (int i = 0; i < nodes; i++) {
            if (supply[i] > 0) {
                mcf.addEdge(s, i, supply[i], 0);
                totalPositive += supply[i];
            } else if (supply[i] < 0) {
                mcf.addEdge(i, t, -supply[i], 0);
            }
        }

        int flowCost = mcf.minCostFlow(s, t, totalPositive);
        long answer = boundaryCost + flowCost;
        System.out.println(answer);
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 0 / 63