제출 #1147972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147972		shaiel_vargas	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	79 ms	12624 KiB

joi2019_ho_t4

import java.util.*;

public class joi2019_ho_t4 {
    
    static class Coin {
        int x, y;

        public Coin(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int manhattanDistance(Coin other) {
            return Math.abs(this.x - other.x) + Math.abs(this.y - other.y);
        }
    }

    public static int solve(int N, List<Coin> coins) {
        List<Coin> targets = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            targets.add(new Coin(i, 1));
            targets.add(new Coin(i, 2));
        }

        int[][] costMatrix = new int[2 * N][2 * N];
        for (int i = 0; i < 2 * N; i++) {
            for (int j = 0; j < 2 * N; j++) {
                costMatrix[i][j] = coins.get(i).manhattanDistance(targets.get(j));
            }
        }

        return hungarianAlgorithm(costMatrix);
    }

    public static int hungarianAlgorithm(int[][] cost) {
        int n = cost.length;
        int[] lx = new int[n];
        int[] ly = new int[n];
        int[] xy = new int[n];
        int[] yx = new int[n];
        boolean[] S = new boolean[n];
        boolean[] T = new boolean[n];
        int[] slack = new int[n];
        int[] slackx = new int[n];

        Arrays.fill(lx, Integer.MIN_VALUE);
        Arrays.fill(ly, 0);
        Arrays.fill(xy, -1);
        Arrays.fill(yx, -1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                lx[i] = Math.max(lx[i], cost[i][j]);
            }
        }

        for (int root = 0; root < n; root++) {
            Arrays.fill(S, false);
            Arrays.fill(T, false);
            Arrays.fill(slack, Integer.MAX_VALUE);
            int x = root;
            int y = -1;
            xy[x] = -1;
            yx[y] = -1;

            while (true) {
                int curX = x;
                int curY = -1;
                int minSlack = Integer.MAX_VALUE;
                for (int j = 0; j < n; j++) {
                    if (!T[j]) {
                        int diff = lx[curX] + ly[j] - cost[curX][j];
                        if (diff < slack[j]) {
                            slack[j] = diff;
                            slackx[j] = curX;
                        }
                    }
                }

                for (int j = 0; j < n; j++) {
                    if (xy[curX] == -1) {
                        break;
                    }
                    curY = xy[curX];
                    curX = slackx[curY];
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        List<Coin> coins = new ArrayList<>(2 * N);

        for (int i = 0; i < 2 * N; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            coins.add(new Coin(x, y));
        }

        int result = solve(N, coins);
        System.out.println(result);
    }
}

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