RT
本蒟蒻开始学习二分兔了,上午比着题解蒙蒙的打出二分图最大匹配的模板之后就开始做题,做到了一个二分图最大权值匹配的题目,题解里说要先学BFS匈牙利算法,匈牙利算法我会
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,e,x,y,match[501];
vector<int> vec[501];
bitset<501> vis;
int dfs(int x)
{
for(int i=0;i<vec[x].size();i++)
{
int nxt=vec[x][i];
if(vis[nxt]) continue ;
vis[nxt]=1;
if(!match[nxt] || dfs(match[nxt]))
{
match[nxt]=x;
return 1;
}
}
return 0;
}
signed main(){
cin>>n>>m>>e;
for(int i=1;i<=e;i++)
{
cin>>x>>y;
vec[x].push_back(y);
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans+=dfs(i);
vis.reset();
}
cout<<ans;
}
但是BFS匈牙利是什么啊,和这个有什区别吗(时间上的,功能上的)