디닉 알고리즘 ( Java )

DinicMaxflow 에 return flow 하면 최대유량 구할수있음.
Graph 클래스에 size 는 없어도 됨.

class Edge {
    public int v;
    public int flow;
    public int C;
    public int rev;

    public Edge(int v, int flow, int C, int rev) {
        this.v = v;
        this.flow = flow;
        this.C = C;
        this.rev = rev;
    }
}

class Graph {
    private int V;
    private int[] level;
    private List<Edge>[] adj;
    private int size; // 없어도됨.

    public Graph(int V , int size) {
        adj = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<Edge>();
        }
        this.V = V;
        this.size = size;
        level = new int[V];
    }

    public void addEdge(int u, int v, int C) {
        Edge a = new Edge(v, 0, C, adj[v].size());
        Edge b = new Edge(u, 0, 0, adj[u].size());

        adj[u].add(a);
        adj[v].add(b);
    }

    public boolean BFS(int s, int t) {
        for (int i = 0; i < V; i++) {
            level[i] = -1;
        }

        level[s] = 0;
        LinkedList<Integer> q = new LinkedList<Integer>();
        q.add(s);

        ListIterator<Edge> i;
        while (q.size() != 0) {
            int u = q.poll();

            for (i = adj[u].listIterator(); i.hasNext();) {
                Edge e = i.next();
                if (level[e.v] < 0 && e.flow < e.C) {
                    level[e.v] = level[u] + 1;
                    q.add(e.v);
                }
            }
        }

        return level[t] >= 0;
    }

    public int sendFlow(int u, int flow, int t, int start[]) {

        if (u == t) {
            return flow;
        }

        for (; start[u] < adj[u].size(); start[u]++) {

            Edge e = adj[u].get(start[u]);

            if (level[e.v] == level[u] + 1 && e.flow < e.C) {
                int curr_flow = Math.min(flow, e.C - e.flow);
                int temp_flow = sendFlow(e.v, curr_flow, t, start);

                if (temp_flow > 0) {
                    e.flow += temp_flow;
                    adj[e.v].get(e.rev).flow -= temp_flow;
                    return temp_flow;
                }
            }
        }

        return 0;
    }

    public void DinicMaxflow(int s, int t) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        if (s == t) {
            return;
        }
        int total = 0;
        while (BFS(s, t)) {
            int[] start = new int[V + 1];
            while (true) {
                int flow = sendFlow(s, Integer.MAX_VALUE, t, start);
                if (flow == 0) {
                    break;
                }
                total += flow;
            }
        }

        bw.write(Integer.toString(total));
        ArrayList<Integer> A = new ArrayList<>();
        ArrayList<Integer> B = new ArrayList<>();
        bw.newLine();
        for (int i = 1 ; i <= size; i++) {
            if (level[i]>0) {
                A.add(i);
            } else {
                B.add(i);
            }
        }

        for (Integer integer : A) {
            bw.write(Integer.toString(integer)+" ");
        }
        bw.newLine();
        for (Integer integer : B) {
            bw.write(Integer.toString(integer)+" ");
        }
        bw.newLine();
        bw.flush();
    }
}