Submission #1148119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148119		ruben_ipenza	Coin Collecting (JOI19_ho_t4)	Java	Compilation error	0 ms	0 KiB

joi2019_ho_t4

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

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

    static class MinCostMaxFlow {
        private final int V;
        private List<Edge>[] graph;
        private int[] dist, prevNode, prevEdge;
        private boolean[] inQueue;

        public MinCostMaxFlow(int V) {
            this.V = V;
            graph = new ArrayList[V];
            for (int i = 0; i < V; i++) graph[i] = new ArrayList<>();
        }

        public void addEdge(int from, int to, int capacity, int cost) {
            graph[from].add(new Edge(to, capacity, cost, graph[to].size()));
            graph[to].add(new Edge(from, 0, -cost, graph[from].size() - 1));
        }

        public int minCostMaxFlow(int source, int sink, int flowLimit) {
            int flow = 0, cost = 0;
            while (flow < flowLimit) {
                dist = new int[V];
                Arrays.fill(dist, Integer.MAX_VALUE);
                prevNode = new int[V];
                prevEdge = new int[V];
                inQueue = new boolean[V];

                Queue<Integer> queue = new LinkedList<>();
                queue.add(source);
                dist[source] = 0;
                inQueue[source] = true;

                while (!queue.isEmpty()) {
                    int u = queue.poll();
                    inQueue[u] = false;
                    for (int i = 0; i < graph[u].size(); i++) {
                        Edge e = graph[u].get(i);
                        if (e.capacity > 0 && dist[u] + e.cost < dist[e.to]) {
                            dist[e.to] = dist[u] + e.cost;
                            prevNode[e.to] = u;
                            prevEdge[e.to] = i;
                            if (!inQueue[e.to]) {
                                queue.add(e.to);
                                inQueue[e.to] = true;
                            }
                        }
                    }
                }

                if (dist[sink] == Integer.MAX_VALUE) break;

                int f = flowLimit - flow;
                for (int v = sink; v != source; v = prevNode[v]) {
                    f = Math.min(f, graph[prevNode[v]].get(prevEdge[v]).capacity);
                }

                flow += f;
                cost += f * dist[sink];

                for (int v = sink; v != source; v = prevNode[v]) {
                    Edge e = graph[prevNode[v]].get(prevEdge[v]);
                    e.capacity -= f;
                    graph[v].get(e.rev).capacity += f;
                }
            }
            return cost;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());

        int totalCoins = 2 * N;
        int[][] coins = new int[totalCoins][2];

        for (int i = 0; i < totalCoins; i++) {
            String[] input = reader.readLine().split(" ");
            coins[i][0] = Integer.parseInt(input[0]);
            coins[i][1] = Integer.parseInt(input[1]);
        }

        List<int[]> targets = new ArrayList<>();
        for (int x = 1; x <= N; x++) {
            for (int y = 1; y <= 2; y++) {
                targets.add(new int[]{x, y});
            }
        }

        int V = totalCoins + N * 2 + 2;
        int source = V - 2, sink = V - 1;
        MinCostMaxFlow mcmf = new MinCostMaxFlow(V);

        for (int i = 0; i < totalCoins; i++) {
            mcmf.addEdge(source, i, 1, 0);
        }

        for (int j = 0; j < targets.size(); j++) {
            mcmf.addEdge(totalCoins + j, sink, 1, 0);
        }

        for (int i = 0; i < totalCoins; i++) {
            for (int j = 0; j < targets.size(); j++) {
                int cost = Math.abs(coins[i][0] - targets.get(j)[0]) + Math.abs(coins[i][1] - targets.get(j)[1]);
                mcmf.addEdge(i, totalCoins + j, 1, cost);
            }
        }

        int result = mcmf.minCostMaxFlow(source, sink, totalCoins);
        System.out.println(result);
    }
}

Compilation message (stderr)

joi2019_ho_t4.java:4: error: class Main is public, should be declared in a file named Main.java
public class Main {
       ^
Note: joi2019_ho_t4.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error

=======