AcWing 1394. 完美牛棚 Java版
原题链接
中等
作者:
辣条_9
,
2024-12-10 16:31:04
,
所有人可见
,
阅读 1
// 匈牙利算法
import java.util.*;
public class Main {
static int N = 210, M = 40010;
static int n,m;
static int [] match = new int [N];//房间匹配的奶牛
static boolean [] use = new boolean[N];//本次匹配房间是否访问过
static int [] h = new int [N],e = new int [M],ne = new int [M];
static int idx = 1;
// a表示奶牛编号,b表示房间编号
static void add(int a,int b){
e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
static boolean find(int x){
// 遍历与x匹配的房间
for(int i = h[x];i != 0;i = ne[i]){
int j = e[i];//与x匹配的房间号
if(!use[j]){// 如果本次匹配房间没访问过
use[j] = true; // 标记本次访问
// j房间没使用过 || j房间的奶牛可以找到新的房间
if(match[j]==0 || find(match[j])){
match[j] = x;
return true;
}
}
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();m = sc.nextInt();
for(int i = 1;i <= n;i++){
int s = sc.nextInt();
while(s-->0){
int b = sc.nextInt();
add(i,b);
}
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
// 每次匹配房间访问情况都要清空
Arrays.fill(use, false);
if(find(i)) cnt++;
}
System.out.println(cnt);
}
}