ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[匈牙利算法模板]P3386二分图最大匹配

2022年9月12日 163点热度 1人点赞 0条评论

题目传送门:P3386 【模板】二分图最大匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路 / Thought

关于二分图的最大匹配,参考以下文章:

算法学习笔记(5):匈牙利算法 - 知乎 (zhihu.com)

最大匹配的思路可以这么理解:dfs(x)函数是用于判断x能否在另一边占到坑位,如果能那就占着,如果已经有人了就看能不能让这人去别的地方,如果可以就占着,否则就不能,没有坑位可占。

需要一个vis数组并在每一次dfs前重置,use表示这个点被谁占了。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 509;
vector<int> g[maxn], use(maxn);
set<pair<int, int> > edges_st;
bitset<maxn * 2> vis;

bool dfs(int x)//表示是否能够占到坑位 
{
	for(auto &i : g[x])
	{
		if(!vis[i])
		{
			vis[i] = true;
			if(!use[i] || dfs(use[i]))return use[i] = x, true;
		}
	}
	return false;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int N, M, E;cin >> N >> M >> E;
	
	
	while(E --)
	{
		int x, y;cin >> x >> y;
		if(edges_st.count({x, y}))continue;
		g[x].push_back(y);
		edges_st.insert({x, y});
	}
	
	int ans = 0;
	for(int i = 1;i <= N; ++ i)
	{
		vis.reset();
		if(dfs(i))ans ++;
	}
	cout << ans << '\n';
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 二分图 匈牙利 最大匹配 洛谷
最后更新:2022年9月12日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号