Multiassignment problem

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

public class MinCostMaxFlow {
    FastScanner in;
    PrintWriter out;

    class MinCostMaxFlowGraph {
        int n;
        ArrayList<Edge>[] g;

        class Edge {
            int from, to;
            long cap, flow, cost;
            Edge rev;

            public Edge(int from, int to, long cap, long flow, long cost) {
                super();
                this.from = from;
                this.to = to;
                this.cap = cap;
                this.flow = flow;
                this.cost = cost;
            }
        }

        class Vertex implements Comparable<Vertex> {
            int v;
            Edge e;
            long d;

            public Vertex(int v) {
                super();
                this.v = v;
            }

            @Override
            public int compareTo(Vertex o) {
                return d < o.d ? -1 : d > o.d ? 1 : v - o.v;
            }

        }

        public MinCostMaxFlowGraph(int n) {
            super();
            this.n = n;
            g = new ArrayList[n];
            for (int i = 0; i < n; i++)
                g[i] = new ArrayList<Edge>();
        }

        public void addEdge(int fr, int to, int cap, long cost) {
            Edge e1 = new Edge(fr, to, cap, 0, cost);
            Edge e2 = new Edge(to, fr, 0, 0, -cost);
            e1.rev = e2;
            e2.rev = e1;
            g[fr].add(e1);
            g[to].add(e2);
        }

        public long[] getMinCostMaxFlow(int source, int target) {
            long[] h = new long[n];
            for (boolean changed = true; changed;) {
                changed = false;
                for (int i = 0; i < n; i++) {
                    for (Edge e : g[i]) {
                        if (e.cap > 0 && h[e.to] > h[e.from] + e.cost) {
                            h[e.to] = h[e.from] + e.cost;
                            changed = true;
                        }
                    }
                }
            }
            Vertex[] vertices = new Vertex[n];
            long[] d = new long[n];
            for (int i = 0; i < vertices.length; i++) {
                vertices[i] = new Vertex(i);
            }
            int flow = 0;
            long cost = 0;
            while (true) {
                dijkstra(source, vertices, d, h);
                if (d[target] == Long.MAX_VALUE) {
                    break;
                }
                long addFlow = Long.MAX_VALUE;
                Vertex v = vertices[target];
                while (v != vertices[source]) {
                    addFlow = Math.min(addFlow, v.e.cap - v.e.flow);
                    v = vertices[v.e.from];
                }
                cost += (d[target] + h[target] - h[source]) * addFlow;
                flow += addFlow;
                v = vertices[target];
                while (v != vertices[source]) {
                    v.e.flow += addFlow;
                    v.e.rev.flow -= addFlow;
                    v = vertices[v.e.from];
                }
                for (int i = 0; i < n; i++) {
                    h[i] += d[i] == Long.MAX_VALUE ? 0 : d[i];
                }
            }
            return new long[] { flow, cost };
        }

        void dijkstra(int source, Vertex[] vertices, long[] d, long[] h) {
            TreeSet<Vertex> ts = new TreeSet<Vertex>();
            Arrays.fill(d, Long.MAX_VALUE);
            for (int i = 0; i < vertices.length; i++) {
                vertices[i].d = Long.MAX_VALUE;
            }
            d[source] = 0;
            vertices[source].d = 0;
            ts.add(vertices[source]);
            while (!ts.isEmpty()) {
                Vertex v = ts.pollFirst();
                for (Edge e : g[v.v]) {
                    if (e.flow >= e.cap) {
                        continue;
                    }
                    if (d[e.to] == Long.MAX_VALUE
                            || d[e.to] > d[e.from] + e.cost + h[e.from]
                                    - h[e.to]) {
                        if (e.cost + h[e.from] - h[e.to] < 0) {
                            throw new AssertionError();
                        }
                        if (ts.contains(vertices[e.to])) {
                            ts.remove(vertices[e.to]);
                        }
                        d[e.to] = d[e.from] + e.cost + h[e.from] - h[e.to];
                        vertices[e.to].d = d[e.to];
                        vertices[e.to].e = e;
                        ts.add(vertices[e.to]);
                    }
                }
            }
        }
    }

    class Kuhn {
        int n;
        boolean[] used;
        int[] left;

        ArrayList<Integer>[] g;

        public void addEdge(int fr, int to) {
            g[fr].add(to);
        }

        public Kuhn(int n) {
            super();
            this.n = n;
            used = new boolean[n];
            left = new int[n];
            g = new ArrayList[n];
            for (int i = 0; i < n; i++)
                g[i] = new ArrayList<Integer>();
        }

        boolean tryKuhn(int v) {
            if (used[v])
                return false;
            used[v] = true;
            for (int i = 0; i < g[v].size(); ++i) {
                int to = g[v].get(i);
                if (left[to] == -1 || tryKuhn(left[to])) {
                    left[to] = v;
                    return true;
                }
            }
            return false;
        }

        boolean solve() {
            Arrays.fill(left, -1);
            for (int v = 0; v < n; ++v) {
                Arrays.fill(used, false);
                tryKuhn(v);
            }

            for (int i = 0; i < n; i++)
                if (left[i] == -1)
                    return false;
            return true;
        }

    }

    void solve() {
        int n = in.nextInt();
        int k = in.nextInt();
        MinCostMaxFlowGraph mm = new MinCostMaxFlowGraph(2 * (n + 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                mm.addEdge(i, j + n, 1, in.nextInt());
            }
        }
        for (int i = 0; i < n; i++)
            mm.addEdge(2 * n, i, k, 0);
        for (int i = n; i < 2 * n; i++)
            mm.addEdge(i, 2 * n + 1, k, 0);
        out.println(mm.getMinCostMaxFlow(2 * n, 2 * n + 1)[1]);
        Kuhn kuhn = new Kuhn(n);
        for (int i = 0; i < n; i++)
            for (MinCostMaxFlowGraph.Edge e : mm.g[i]) {
                if (e.flow > 0)
                    kuhn.addEdge(i, e.to - n);
            }
        for (int i = 0; i < k; i++) {
            kuhn.solve();
            int[] ans = new int[n];
            for (int j = 0; j < n; j++) {
                ans[kuhn.left[j]] = j;
            }
            for (int j = 0; j < n; j++)
                out.print((ans[j] + 1) + " ");
            for (int j = 0; j < n; j++)
                for (int kk = 0; kk < kuhn.g[j].size(); kk++)
                    if (kuhn.g[j].get(kk) == ans[j])
                        kuhn.g[j].remove(kk);
            out.println();
        }
    }

    void run() {
        try {
            in = new FastScanner(new File("multiassignment.in"));
            out = new PrintWriter(new File("multiassignment.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void runIO() {

        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }

    public static void main(String[] args) {
        new MinCostMaxFlow().run();
    }
}