# 二分图（匈牙利算法）

10/17 14:14

``````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();
}
}

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