[洛谷P3386] [模板] 二分图匹配 (匈牙利算法)
2024-09-04 08:40:16
毒瘤出题人zzk出了个二分图匹配的题(18.10.04模拟赛T2),逼我来学二分图匹配。
网络流什么的llx讲完之后有点懵,还是匈牙利比较好理解(绿与被绿)。
对于左边的点一个一个匹配,记录右边哪个点跟左边的i匹配:cp[i]
如果还没有配对,就直接配上。
如果已经有匹配了,每次dfs找增广路(看看能不能换一下),如果成功,那么匹配数增加一。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int n,m,ec,ans;
int e[][];
int cp[];
int used[]; int dfs(int p)
{
for(int i=;i<=m;i++)
{
if(!used[i]&&e[p][i])
{
used[i]=;
if(!cp[i]||dfs(cp[i]))
{
cp[i]=p;
return ;
}
}
}
return ;
} void hungary()
{
ans=;
for(int i=;i<=n;i++)
{
memset(used,,sizeof(used));
if(dfs(i))ans++;
}
} int main()
{
scanf("%d%d%d",&n,&m,&ec);
for(int i=;i<=ec;i++)
{
int a,b;
scanf("%d%d",&a,&b);
e[a][b]=;
}
hungary();
printf("%d",ans);
return ;
}
最新文章
- LINQ to SQL语句(17)之对象加载
- mysql中价格用什么数据类型表示最佳?
- Java堆内存的十个要点
- h5 range应用 透明度+RGB
- SQL SERVER索引
- CoffeeScript飞一样的写javascript
- clang和gcc消除警告
- treeview递归
- Orchard开源ASP.NET MVC CMS简介
- $_SERVER参数的含义
- MySQL日志系统
- [BNUZOJ1261][ACM][2016北理校赛]方块消除(栈,字符串)
- PHP怎么打开或者关闭文件?
- 基于Apache axis2开发Java Web服务
- ceph使用对象网关
- CSS3之实现光润效果
- Eclipse搭建服务器,实现与Android的简单通信
- linux配置gitlab步骤
- [转]让iframe自适应高度-真正解决
- [zz] MATLAB工具箱介绍
热门文章
- This inspection highlights chained comparisons that can be simplified.
- JNI的第1种写法 及 JNI通过形参修改Java数据
- 开启新项目时启动tomcat的一个小问题
- Django专题-AJAX
- Python 学习笔记:Python 连接 SQL Server 报错(20009, b&#39;DB-Lib error message 20009, severity 9)
- JS 判断移动端与PC端
- NSPredicate 应用
- elasticsearch 大集群,双重别名,滚动更新分词方案
- CI_CD(jenkins)公司实战_未完成版
- Okhttp教程 (1)