【笔记】数据结构与算法之匈牙利算法

QingYi.

[Java] 纯文本查看 复制代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 510;
    static int M = 100010;
    static int n1,n2,m,idx;
    static int [] h = new int[N];
    static int [] ne = new int[M];
    static int [] e = new int[M];
    //匹配的数值
    static int [] match = new int[N];
    //状态statue
    static boolean [] st = new boolean[N];

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] s = bf.readLine().split(" ");
        n1 = Integer.parseInt(s[0]);
        n2 = Integer.parseInt(s[1]);
        m = Integer.parseInt(s[2]);
        Arrays.fill(h,-1);
        while (m-- > 0){
            String[] res = bf.readLine().split(" ");
            int a = Integer.parseInt(res[0]);
            int b = Integer.parseInt(res[1]);
            add(a,b);
        }
        int res = 0;

        for(int i = 1;i<=n1;i++){
            //find函数会改变，每次都要置为false
            Arrays.fill(st,false);
            if (find(i)){
                res++;
            }
        }
        System.out.println(res);
    }

    private static boolean find(int x) {
        for(int i = h[x];i!=-1;i = ne[i]){
            int j = e [i];

            if (!st[j]){
                //没访问过就设置访问过
                st[j] = true;
                //没有匹配或者当前这个点的上一级没有匹配过
                if (match[j]==0 || find(match[j])){
                    match[j] = x;
                    return true;
                }
            }
        }
        return false;
    }

    private static void add(int a, int b) {
        e[idx] =b;
        ne[idx] = h[a];
        h[a] = idx++;

    }
}

在新标签打开所有链接复制所有链接URL复制所有链接URL（反向）复制所有链接标题 + URL复制所有链接标题 + URL (MD)复制所有链接标题 + URL (BBS)复制所有链接标题 + URL (筛选)复制所有链接标题 + URL (设置复制格式)在新标签页打开所有图片链接在一个标签页显示所有图片链接
复选框 - 选中
复选框 - 取消
复选框 - 反选
单选框 - 选中
单选框 - 取消
特殊单选框 - 选中