求助二分图
  • 板块灌水区
  • 楼主CuSO4_and_5H2O
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/7/24 20:26
  • 上次更新2023/10/27 18:35:31
查看原帖
求助二分图
231946
CuSO4_and_5H2O楼主2022/7/24 20:26

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匈牙利是什么啊,和这个有什区别吗(时间上的,功能上的)

2022/7/24 20:26
加载中...