/*************************************************************************
 *  Kompilacja:  javac AssignmentProblem.java
 *  Wykonanie:    java AssignmentProblem N
 *  Zależności: DijkstraSP.java DirectedEdge.java
 *
 *  Rozwiązuje problem przypisania N na N w czasie N^3 log N za pomocą
 *  algorytmu wykrywania najkrótszej ścieżki.
 *
 *  Uwaga: można użyć "gęstej" wersji algorytmu Dijsktry, aby uzyskać
 *  teoretycznie lepszą wydajność równą N^3, jednak w praktyce nie 
 *  przynosi to korzyści.
 *
 *  Zakładamy, że macierz kosztów N na N jest nieujemna.
 *
 *
 *********************************************************************/

public class AssignmentProblem {
    private static final int UNMATCHED = -1;

    private int N;              // Liczba wierszy i kolumn.
    private double[][] weight;  // Macierz kosztów N na N.
    private double[] px;        // px[i] = zmienna dla wiersza i.
    private double[] py;        // py[j] = zmienna dla kolumny j.
    private int[] xy;           // xy[i] = j oznacza, że i-j pasują do siebie.
    private int[] yx;           // yx[j] = i oznacza, że i-j pasują do siebie.

 
    public AssignmentProblem(double[][] weight) {
        N = weight.length;
        this.weight = new double[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                this.weight[i][j] = weight[i][j];

        // Zmienne.
        px = new double[N];
        py = new double[N];

        // Początkowo nie ma dopasowań
        xy = new int[N];
        yx = new int[N];
        for (int i = 0; i < N; i++) xy[i] = UNMATCHED;
        for (int j = 0; j < N; j++) yx[j] = UNMATCHED;

        for (int k = 0; k < N; k++) {
            System.out.println(k);
            assert isDualFeasible();
            assert isComplementarySlack();
            augment();
        }
        assert check();
    }

    // Znajdowanie najkrótszej ścieżki powiększającej i aktualizowanie danych
    private void augment() {

        // Tworzenie grafu rezydualnego
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(2*N+2);
        int s = 2*N, t = 2*N+1;
        for (int i = 0; i < N; i++) {
            if (xy[i] == UNMATCHED) G.addEdge(new DirectedEdge(s, i, 0.0));
        }
        for (int j = 0; j < N; j++) {
            if (yx[j] == UNMATCHED) G.addEdge(new DirectedEdge(N+j, t, py[j]));
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (xy[i] == j) G.addEdge(new DirectedEdge(N+j, i, 0.0));
                else            G.addEdge(new DirectedEdge(i, N+j, reduced(i, j)));
            }
        }

        // Wyznaczanie najkrótszej ścieżki z s do każdego innego wierzchołka
        DijkstraSP spt = new DijkstraSP(G, s);

        // Powiększanie wzdłuż kolejnych ścieżek
        for (DirectedEdge e : spt.pathTo(t)) {
            int i = e.from(), j = e.to() - N;
            if (i < N) {
                xy[i] = j;
                yx[j] = i;
            }
        }

        // Aktualizowanie zmiennych dualnych
        for (int i = 0; i < N; i++) px[i] += spt.distTo(i);
        for (int j = 0; j < N; j++) py[j] += spt.distTo(N+j);
    }

    // Zmniejszony koszt dla i-j
    private double reduced(int i, int j) {
        return weight[i][j] + px[i] - py[j];
    }

    // Łączna waga idealnego dopasowania o minimalnej wadzie	
    public double weight() {
        double total = 0.0;
        for (int i = 0; i < N; i++) {
            if (xy[i] != UNMATCHED)
                total += weight[i][xy[i]];
        }
        return total;
    }

    public int sol(int i) {
        return xy[i];
    }

    // Sprawdzanie, czy zmienne są dopuszczalnym rozwiązaniem zadania dualnego
    private boolean isDualFeasible() {
        // Sprawdzanie, czy zmniejszenie kosztu we wszystkich krawędziach jest >= 0
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (reduced(i, j) < 0) {
                    System.out.println("Zmienne nie są dopuszczalnym rozwiązaniem zadania dualnego");
                    return false;
                }
            }
        }
        return true;
    }

    // Sprawdzanie, czy zmienne pierwotne i dualne są uzupełniające
    private boolean isComplementarySlack() {
        
        for (int i = 0; i < N; i++) {
            if ((xy[i] != UNMATCHED) && (reduced(i, xy[i]) != 0)) {
                System.out.println("Zmienne pierwotne i dualne nie są uzupełniające");
                return false;
            }
        }
        return true;
    }

    // Sprawdzanie, czy dla zmiennych podstawowych dopasowanie jest idealne
    private boolean isPerfectMatching() {

        // Sprawdzanie, czy xy[] jest idealnym dopasowaniem.
        boolean[] perm = new boolean[N];
        for (int i = 0; i < N; i++) {
            if (perm[xy[i]]) {
                System.out.println("Nie jest to idealne dopasowanie");
                return false;
            }
            perm[xy[i]] = true;
        }

        // Sprawdzanie, czy xy[] i yx[] to odwrotności.
        for (int j = 0; j < N; j++) {
            if (xy[yx[j]] != j) {
                System.out.println("xy[] i yx[] nie są odwrotnościami");
                return false;
            }
        }
        for (int i = 0; i < N; i++) {
            if (yx[xy[i]] != i) {
                System.out.println("xy[] i yx[] nie są odwrotnościami");
                return false;
            }
        }

        return true;
    }


    // Sprawdzanie warunków optymalności.
    private boolean check() {
        return isPerfectMatching() && isDualFeasible() && isComplementarySlack();
    }

    public static void main(String[] args) {

        int N = Integer.parseInt(args[0]);
        double[][] weight = new double[N][N];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                weight[i][j] = Math.random();

        AssignmentProblem assignment = new AssignmentProblem(weight);
        StdOut.println("waga = " + assignment.weight());
        for (int i = 0; i < N; i++)
            StdOut.println(i + "-" + assignment.sol(i));
    }

}
