社区讨论
二分图最大匹配求找错
学术版参与者 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 条回复,欢迎继续交流。
正在加载回复...