二分图(匈牙利算法)

10/17 14:14
阅读数 25
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    private static int index = 0;

    private static int[] end;

    private static int[] lastEdge;

    private static int[] previousEdge;

    private static int[] selectedStudent;

    private static boolean[] isCourseSelected;

    private static boolean dfs(int s) {

        for (int edge = lastEdge[s]; edge != 0; edge = previousEdge[edge]) {

            int p = end[edge];

            if (! isCourseSelected[p]) {
                isCourseSelected[p] = true;
                if (selectedStudent[p] == 0 || dfs(selectedStudent[p])) {
                    selectedStudent[p] = s;
                    return true;
                }
            }
        }

        return false;
    }

    private static void init(int n, int p) {

        int edges = n * p;
        int nodes = Math.max(p, n);

        index = 0;
        end = new int[edges + 1];
        lastEdge = new int[nodes + 1];
        previousEdge = new int[edges + 1];

        selectedStudent = new int[p + 1];
        isCourseSelected = new boolean[p + 1];
    }

    private static void addEdge(int a, int b) {
        end[++ index] = b;
        previousEdge[index] = lastEdge[a];
        lastEdge[a] = index;
    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {

            int T = in.nextInt();

            while (T -- > 0) {

                int p = in.nextInt();
                int n = in.nextInt();

                init(n, p);

                for (int i = 1; i <= p; ++ i) {
                    int nums = in.nextInt();
                    while (nums -- > 0) {
                        int j = in.nextInt();
                        addEdge(j, i);
                    }
                }

                int res = 0;

                for (int i = 1; i <= n; ++ i) {
                    Arrays.fill(isCourseSelected, false);

                    if (dfs(i)) {
                        res ++;
                    }
                }

                if (res == p) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部