社区讨论

二分图最大匹配求找错

学术版参与者 3已保存回复 5

讨论操作

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

当前回复
5 条
当前快照
1 份
快照标识符
@lo7jp14c
此快照首次捕获于
2023/10/27 02:56
2 年前
此快照最后确认于
2023/10/27 02:56
2 年前
查看原帖
rt
luogu的模板题过去了,但是入门与面试题库里面那个二分图匹配wa了3个点
CPP
#include<bits/stdc++.h>
using namespace std;
int nl,nr,m;
struct edge{
	int to,fl;
}e[500005];
vector<int>p[20005];
int head = 1;
int dis[20005];
#define ss nl+nr+1
#define tt nl+nr+2
bool bfs(){
	memset(dis,31,sizeof(dis));
	int mx = dis[0];
	dis[ss] = 0;
	queue<int>q;
	q.push(ss);
	while(!q.empty()){
		int now = q.front();q.pop();
		//cout<<now<<endl;
		for(int i =0;i<p[now].size();i++){
			if(e[p[now][i]].fl!=0 and dis[e[p[now][i]].to] == mx){
				dis[e[p[now][i]].to] = dis[now]+1;
				q.push(e[p[now][i]].to);
			}
		}
	}return (dis[tt]!=mx);
}int dfs(int now,int f){
	//cout<<now<<' '<<f<<endl;
	if(!f or now == tt)return f;
	int res =0;
	for(int i =0;i<p[now].size();i++){
		//cout << e[p[now][i]].to << endl;;
		if(dis[e[p[now][i]].to] == dis[now]+1 and e[p[now][i]].fl!=0){
			int nw;
			if((nw = dfs(e[p[now][i]].to,min(e[p[now][i]].fl,f)))){
				e[p[now][i]].fl-=nw,e[p[now][i]^1].fl+=nw,f-=nw,res+=nw;
				if(!nw)break;
			}
		}
	}return res;
}
signed main(){
	cin>>nl>>nr>>m;
	for(int i =1;i<=m;i++){
		int a,b;
		cin>> a>>b;
		b+=nl;
		e[++head].to = b,e[head].fl = 1;
		p[a].push_back(head);
		e[++head].to = a,e[head].fl = 0;
		p[b].push_back(head);
	}for(int i = 1;i<=nl;i++){
		e[++head].to = i,e[head].fl = 1;
		p[ss].push_back(head);
		e[++head].to = ss,e[head].fl = 0;
		p[i].push_back(head);
	}for(int i = nl+1;i<=nl+nr;i++){
		e[++head].to = i,e[head].fl = 0;
		p[tt].push_back(head);
		e[++head].to = tt,e[head].fl = 1;
		p[i].push_back(head);
	}int ans =0;
	for(;;){
		if(!bfs())break;
		int nw = dfs(ss,10000000);
		if(!nw)break;
		ans+=nw;
	}cout<<ans<<endl;
	return 0;
}

回复

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

正在加载回复...