社区讨论

RE求助玄一关

P3386【模板】二分图最大匹配参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lw4ubbch
此快照首次捕获于
2024/05/13 18:47
2 年前
此快照最后确认于
2024/05/13 21:01
2 年前
查看原帖
using namespace std;
int e[53232],ne[53032],idx,h[52332];
int fin[51332];
int match[53302];
int ans=0;
int vis[50132];
int add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n,m;
bool find(int x){
	for(int i=h[x];i!=-1;i=ne[i]){
	int j=e[i];
	if(!vis[j]){
	vis[j]=true;
		if(!match[j]||find(match[j])){
		match[j]=x;
		return true;
	}
	}
	}
	return false;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int q;
	cin>>n>>m;
	cin>>q;
	memset(h,-1,sizeof h);
	while(q--){
		int a,b;
		cin>>a>>b;
		add(a,b);
	}
	for(int i=1;i<=n;i++){
	memset(vis,0,sizeof vis); 
		if(find(i)) ans++;
	}
	cout<<ans;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...