Submission #1147955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147955		sossa_abel	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	43 ms	10552 KiB

joi2019_ho_t4

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

public class joi2019_ho_t4 {
    static class State {
        int x, y;
        int steps;
        
        State(int x, int y, int steps) {
            this.x = x;
            this.y = y;
            this.steps = steps;
        }
    }
    
    // Implementación del Algoritmo Húngaro para asignación óptima
    static long hungarianAlgorithm(int[][] costMatrix) {
        int n = costMatrix.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];
        int[] prev = new int[n];
        
        Arrays.fill(xy, -1);
        Arrays.fill(yx, -1);
        
        // Inicialización de etiquetas
        for (int x = 0; x < n; x++) {
            lx[x] = costMatrix[x][0];
            for (int y = 1; y < n; y++) {
                lx[x] = Math.max(lx[x], costMatrix[x][y]);
            }
        }
        
        for (int j = 0; j < n; j++) {
            ly[j] = 0;
        }
        
        // Encontrar emparejamiento perfecto
        for (int currentX = 0; currentX < n; currentX++) {
            Arrays.fill(S, false);
            Arrays.fill(T, false);
            Arrays.fill(prev, -1);
            
            for (int y = 0; y < n; y++) {
                slack[y] = lx[currentX] + ly[y] - costMatrix[currentX][y];
                slackx[y] = currentX;
            }
            
            int y = -1;
            while (y == -1) {
                if (!S[currentX]) {
                    S[currentX] = true;
                    for (int j = 0; j < n; j++) {
                        if (!T[j]) {
                            int currentSlack = lx[currentX] + ly[j] - costMatrix[currentX][j];
                            if (currentSlack < slack[j]) {
                                slack[j] = currentSlack;
                                slackx[j] = currentX;
                            }
                        }
                    }
                }
                
                y = findAugmentingPath(costMatrix, lx, ly, xy, yx, S, T, slack, slackx, prev);
                if (y == -1) {
                    updateLabels(lx, ly, S, T, slack, n);
                }
            }
            
            augmentPath(xy, yx, prev, y);
        }
        
        long totalCost = 0;
        for (int x = 0; x < n; x++) {
            totalCost += costMatrix[x][xy[x]];
        }
        return totalCost;
    }
    
    static int findAugmentingPath(int[][] costMatrix, int[] lx, int[] ly, int[] xy, int[] yx,
                                boolean[] S, boolean[] T, int[] slack, int[] slackx, int[] prev) {
        int n = costMatrix.length;
        for (int y = 0; y < n; y++) {
            if (!T[y] && slack[y] == 0) {
                T[y] = true;
                if (yx[y] == -1) {
                    return y;
                }
                S[yx[y]] = true;
                for (int j = 0; j < n; j++) {
                    if (!T[j]) {
                        int currentSlack = lx[yx[y]] + ly[j] - costMatrix[yx[y]][j];
                        if (currentSlack < slack[j]) {
                            slack[j] = currentSlack;
                            slackx[j] = yx[y];
                            prev[j] = y;
                        }
                    }
                }
            }
        }
        return -1;
    }
    
    static void updateLabels(int[] lx, int[] ly, boolean[] S, boolean[] T, int[] slack, int n) {
        int delta = Integer.MAX_VALUE;
        for (int y = 0; y < n; y++) {
            if (!T[y]) {
                delta = Math.min(delta, slack[y]);
            }
        }
        for (int x = 0; x < n; x++) {
            if (S[x]) lx[x] -= delta;
        }
        for (int y = 0; y < n; y++) {
            if (T[y]) ly[y] += delta;
            if (!T[y]) slack[y] -= delta;
        }
    }
    
    static void augmentPath(int[] xy, int[] yx, int[] prev, int y) {
        while (prev[y] != -1) {
            int x = prev[y];
            int ty = xy[x];
            yx[y] = x;
            xy[x] = y;
            y = ty;
        }
    }
    
    static int findShortestPath(int startX, int startY, int targetX, int targetY) {
        return Math.abs(startX - targetX) + Math.abs(startY - targetY);
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        int[][] coins = new int[2*n][2];
        for (int i = 0; i < 2*n; i++) {
            String[] parts = br.readLine().split(" ");
            coins[i][0] = Integer.parseInt(parts[0]);
            coins[i][1] = Integer.parseInt(parts[1]);
        }
        
        // Construir matriz de costos
        int[][] costMatrix = new int[2*n][2*n];
        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});
            }
        }
        
        for (int i = 0; i < 2*n; i++) {
            for (int j = 0; j < 2*n; j++) {
                costMatrix[i][j] = findShortestPath(
                    coins[i][0], coins[i][1],
                    targets.get(j)[0], targets.get(j)[1]
                );
            }
        }
        
        long result = hungarianAlgorithm(costMatrix);
        System.out.println(result);
    }
}

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