AcWing 861. 非诚勿扰牵手成功率最大化算法
原题链接
简单
作者:
季之秋
,
2021-01-23 16:27:43
,
所有人可见
,
阅读 290
非诚勿扰牵手成功率最大化算法
import java.util.*;
public class Main{
static int n1,n2,m,idx,N=100010;
static int match[]=new int[N];//女生牵手对象
static int[] e,ne,h;
static boolean st[]=new boolean[N];//女生有没有被预定
static void init(){//初始化
e=new int[N];
ne=new int[N];
h=new int[N];
Arrays.fill(h,-1);
}
static void add(int a,int b){//男生a心动女生b
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
init();
n1=sc.nextInt();
n2=sc.nextInt();
m=sc.nextInt();
while(m--!=0){
int a=sc.nextInt();
int b=sc.nextInt();
add(a,b);//只有男生可以找女生
}
int ref=0;
for(int i=1;i<=n1;i++){//遍历所有男生,
Arrays.fill(st,false);//刷新每次匹配的预定为false(让每位男生可以选择所有女生)
if(find(i)) ref++;//如果牵手成功就一对情侣
}
System.out.println(ref);//最多有几队情侣
}
static boolean find(int x){//查看x男生能不能牵手成功
for(int i=h[x];i!=-1;i=ne[i]){//看男生的心动女嘉宾
int j=e[i];//女嘉宾j
if(!st[j]){//如果j女生被预定了就下一个心动女生
st[j]=true;//没有预定就先预定j女生
if(match[j]==0||find(match[j])){//j女生没有牵手对象或她对象可以找其他人牵手
match[j]=x;//让这两人牵手
return true;//这个男生牵手成功
}
}
}
return false;//所有女嘉宾都牵手失败就失败了
}
}