AcWing 861. 二分图的最大匹配JAVA
原题链接
简单
作者:
理想二旬.
,
2021-05-19 21:00:16
,
所有人可见
,
阅读 309
JAVA 代码
import java.util.*;
class Main{
//节点个数
static int N = 510;
//边个数
static int M = 100010;
//jb
static int n1, n2, m, idx;
//邻接表
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
//美眉是否被预定
static boolean[] stu = new boolean[N];
//美眉的对象
static int[] match = new int[N];
//邻接表
public static void add(int a, int b){
e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}
//gg找到对象没
public static boolean find(int x){
//gg心仪的美眉
for(int i = h[x]; i != -1; i = ne[i]){
//取出美眉
int j = e[i];
//美眉没被预定
if(stu[j] == false){
//先预定一手
stu[j] = true;
//预定的美眉没对象或者预定的美眉的对象还有其他心仪美眉
if(match[j] == 0 || find(match[j]) == true){
//牵手/挖墙脚
match[j] = x;
//找对象成功
return true;
}
}
}
//555没找到对象
return false;
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
n1 = in.nextInt();
n2 = in.nextInt();
m = in.nextInt();
//初始化邻接表
Arrays.fill(h, -1);
//存图
while(m -- > 0){
int a = in.nextInt();
int b = in.nextInt();
//虽然是无向边,但找对象是个单向运动
add(a, b);
}
//牵手成功的对象个数
int res = 0;
//迭代所有gg
for(int i = 1; i <= n1; i ++){
//每轮迭代都初始化美眉没被预定,这样增加了公平性,可以挖墙脚
Arrays.fill(stu, false);
//牵手成功就++
if(find(i) == true)
res ++;
}
System.out.println(res);
}
}