最大流

• OI Wiki: https://oi-wiki.org/graph/flow/max-flow/

题目	难度
CF489B	rating 1200

Dinic 算法

CF489B

网络流写法 https://codeforces.com/contest/489/submission/243843771

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class CF489B {
    static int n, m;
    static int[] a, b;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        m = scanner.nextInt();
        b = new int[m];
        for (int i = 0; i < m; i++) {
            b[i] = scanner.nextInt();
        }
        System.out.println(solve());
    }

    static int st, end;
    // to, rig, cap
    static List<int[]>[] g;
    static int[] d, iter;

    private static String solve() {
        st = a.length + b.length;
        end = st + 1;
        g = new ArrayList[end + 1];
        Arrays.setAll(g, e -> new ArrayList<>());

        for (int i = 0; i < n; i++) {
            addEdge(st, i, 1);
            for (int j = 0; j < m; j++) {
                if (Math.abs(a[i] - b[j]) < 2) {
                    addEdge(i, j + n, 1);
                }
            }
        }
        for (int j = 0; j < m; j++) {
            addEdge(j + n, end, 1);
        }

        // 从源点 st 出发的距离
        d = new int[g.length];
        // 寻找增广路
        // 当前弧，在其之前的边已经没有用了，避免对没有用的边进行多次检查
        iter = new int[g.length];
        return String.valueOf(dinic());
    }

    static int dfs(int v, int minF) {
        if (v == end) {
            return minF;
        }
        for (; iter[v] < g[v].size(); iter[v]++) {
            int[] e = g[v].get(iter[v]);
            int w = e[0], rid = e[1], cap = e[2];
            if (cap > 0 && d[w] > d[v]) {
                int f = dfs(w, Math.min(minF, cap));
                if (f > 0) {
                    e[2] -= f;
                    g[w].get(rid)[2] += f;
                    return f;
                }
            }
        }
        return 0;
    }

    static int dinic() {
        int maxFlow = 0;
        while (bfs()) {
            iter = new int[g.length];
            while (true) {
                int f = dfs(st, (int) 1e9);
                if (f > 0) {
                    maxFlow += f;
                } else {
                    break;
                }
            }
        }
        return maxFlow;
    }

    static boolean bfs() {
        d = new int[g.length];
        d[st] = 1;
        Queue<Integer> q = new ArrayDeque<>();
        q.add(st);
        while (!q.isEmpty()) {
            int v = q.remove();
            for (int[] e : g[v]) {
                int w = e[0], cap = e[2];
                if (cap > 0 && d[w] == 0) {
                    d[w] = d[v] + 1;
                    q.add(w);
                }
            }
        }
        return d[end] > 0;
    }

    static void addEdge(int from, int to, int cap) {
        g[from].add(new int[]{to, g[to].size(), cap});
        g[to].add(new int[]{from, g[from].size() - 1, 0});
    }
}

（全文完）