（模板）二分图最大匹配，最大流算法_最大匹配--最大流算法-程序员宅基地

技术标签： 模板  图论  网络流  二分图最大匹配  

转换为最大流做即可。注意加边的技巧。
这里写图片描述
代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
struct edge{
    int to,cap,rev;
};
vector<edge>G[2500];
void addedge(int from,int to,int cap)
{
    G[from].push_back(edge{to,cap,(int)G[to].size()});
    G[to].push_back(edge{from,0,(int)G[from].size()-1});
}
int level[2500],iter[2500];
int bfs(int s)
{
    memset(level,-1,sizeof(level));level[s]=0;
    queue<int>que;que.push(s);
    while(!que.empty()){
        int t=que.front();que.pop();
        for(auto i=G[t].begin();i!=G[t].end();i++){
            edge e=*i;
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[t]+1;que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f)
{
    if(v==t)return f;
    for(int&i=iter[v];i<G[v].size();i++){
        edge&e=G[v][i];
        if(e.cap&&level[e.to]>level[v]){
            int d=dfs(e.to,t,min(e.cap,f));
            if(d){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int maxflow(int s,int t)
{
    int flow=0;
    for(;;){
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0, sizeof(iter));
        int f;
        while(f=dfs(s,t,1<<30))
            flow+=f;
    }
}
int main()
{
    int n,m,e,i,j,k;
    cin>>n>>m>>e;
    for(i=1;i<=n;i++)
        addedge(0,i,1);
    for(i=n+1;i<=n+m;i++)
        addedge(i,2020,1);//源点为0，汇点为2020
    for(i=1;i<=e;i++){
        scanf("%d%d",&k,&j);
        if(j>m)continue;
        addedge(k,j+n,1);
    }
    cout<<maxflow(0,2020)<<endl;

    return 0;
}
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/HumveeA6/article/details/79504242

智能推荐

Vscode ESP-IDF插件python工具使用中的路径问题1_eclipse esp-idf 怎么选择python的路径-程序员宅基地

文章浏览阅读390次。bash: otatool.py：未找到命令。_eclipse esp-idf 怎么选择python的路径

在unity中如何高效的使用内置android方法_unity不重复显示androidjavaobject maketext-程序员宅基地

文章浏览阅读6.1k次，点赞6次，收藏24次。目录AndroidJNIAndroidJavaClassAndroidJavaObject简单示例：Unity中如何正确使用AndroidJNIapk接入中经常遇到的问题记录：android 实用UnityAndroid功能汇总1.如何调用Toast2.如何调用相机拍照3.如何调用图库选择图片4.Unity3D调用Android功能与组件(四)——文字、..._unity不重复显示androidjavaobject maketext

Linux网络调试助手-程序员宅基地

文章浏览阅读1k次。Linux网络调试助手_linux网络调试助手

云计算及应用课程知识整理-程序员宅基地

文章浏览阅读1.2k次。文章目录一、云计算云计算概念云计算的服务类型云计算技术体系结构的层次及其功能为什么云计算成本低？二、GFS分布式的文件系统设计需要考虑哪些问题？GFS架构GFS容错机制三、MapReducemapReduce概念MapReduce适合什么类型数据？四、分布式锁服务Chubbychubby功能两阶段决议chubby基本架构五、分布式结构化数据表BigTable是什么架构BigTable中chubby的用途六、分布式存储系统Megastore实现机制融合SQL和noSQL局部索引和全局索引三种图三种副本七、大规

【SLAM】坐标系变换与外参标定-程序员宅基地

文章浏览阅读120次。突然发现学习文档有下面这句话：学习这件事不在乎有没有人教你，最重要的是在于你自己有没有觉悟和恒心。——法布尔task02从二维坐标系开始推导坐标系变换参数，进而加入平移，加入Z轴拓展到三维坐标系的坐标转换方程。同时了解到相机外参对SLAM系统的作用，清楚外参标定常用到的软件。

HTML5游戏引擎Egret发布2.0版 开发工具亦获更新-程序员宅基地

文章浏览阅读62次。5月22日在北京国际会议中心举办的HTML5游戏生态大会上，白鹭时代旗下游戏引擎Egret Engine发布2.0版，同时还发布了Flash转换HTML5工具Egret Conversion、HTML5游戏加速Egret Runtime 2.0、GUI可视化编辑器Egret Wing 2.0、骨骼动画工具DragonBones4.0、富媒体移动开发框架Egret Lark1.0。\\以下是各引擎和...

随便推点

Android逆向 学习Android安全和逆向开发的路线总结(1)-程序员宅基地

文章浏览阅读240次，点赞5次，收藏9次。到了合适的年纪，后续不知道该如何发展，转型管理，还是加强技术研究。如果你有需要，我这里恰好有为什么，不来领取！，到了合适的年纪，后续不知道该如何发展，转型管理，还是加强技术研究。如果大家觉得自己在网上找的资料非常杂乱、不成体系的话，我也分享一套给大家，比较系统，我平常自己也会经常研读。很多朋友不是没有资料，大多都是有几十上百个G，但是杂乱无章，不知道怎么看从哪看起，甚至是看后就忘。**第一，**学习知识比较碎片化，没有合理的学习路线与进阶方向。**第二，**开发几年，不知道如何进阶更进一步，比较迷茫。

基于Java的校园停车场管理系统的设计与实现(源码+lw+部署文档+讲解等)-程序员宅基地

文章浏览阅读828次，点赞20次，收藏16次。博主介绍：全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者，博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战精彩专栏 推荐订阅2023-2024年最值得选的微信小程序毕业设计选题大全：100个热门选题推荐2023-2024年最值得选的Java毕业设计选题大全：500个热门选题推荐Java精品实战案例《500套》微信小程序项目精品案例《500套》文末获取源码+数据库。

html js 图片跑马灯,jquery跑马灯 图片不间断滚动效果-程序员宅基地

文章浏览阅读600次。在网页中为了显示更多内容，界面更美观，通常会用到“跑马灯”效果。打开 Dreamweaver新建 HTML 文档；修改标题为"跑马灯"保存为 index.html 文件。首先，编写跑马灯部分的静态 HTML 代码，把图片排列起来在 和 标签中添加以下代码：　　　　　　　　　　　　　　　　给上一步的 HTML 代码中的 div 标签增加 class 属性，如下：　编写跑马灯部分的 CSS 样式代...

信息技术计算机老师继续教育培训心得,【信息技术继续教育培训心得】_信息技术继续教育培训之收获与感想...-程序员宅基地

文章浏览阅读355次。信息技术继续教育培训之收获与感想常宁市一中 谢玉香我很兴奋参加本次网络培训.人们常说:“活到老,学到”, 信息技术继续教育培训给我们信息技术教师提供了一个很好的平台了——是我们教师提高教育教学水平的绝好机会.形式新颖,效果明显.随着学习的推进,自己对此事的认识,也由被动的迫于形式环境,不得不学,转变为主观上主动的去学习,认为应该学.所以我每天都坚持在线学习、写作业.本人收获很多,感触也颇深.下面..._继续教育培训信息技术

基于springboot的企业门户网站毕设源码_企业门户开源-程序员宅基地

文章浏览阅读288次。此外，基于SpringBoot的开源社区活跃，可以利用众多的开源库和插件快速实现各种功能模块，如权限管理、日志记录、在线支付等，为企业提供全面的信息化解决方案。总之，基于SpringBoot的企业门户网站开发具有显著的优势，可以提高企业的开发效率，降低维护成本，同时提供丰富的功能和良好的用户体验。综上所述，基于SpringBoot的企业门户网站具有快速开发和部署、微服务架构支持、强大的生态系统、前后端分离的开发模式、安全性保障和国际化支持等多个创新点，可以帮助企业提高信息化建设的效率和质量。_企业门户开源

linux执行du等待时间长,Linux_linux磁盘管理命令之：du命令解析，经过长时间的发展，linux磁盘 - phpStudy...-程序员宅基地

文章浏览阅读1.9k次。linux磁盘管理命令之：du命令解析经过长时间的发展，linux磁盘管理命令中df命令的使用，系统管理员想要知道df命令的功能，很多用户对多数linux磁盘管理命令也都有所了解，这里我发表一下个人理解，和大家讨论讨论一下du命令。磁盘配额：看完本文相信您能得到一个满意的答案。linux磁盘管理命令--dudu的英文原义为“disk usage”，含义为显示磁盘空间的使用情况。功能：统计目录(或文..._du太慢

推荐文章

热门文章

相关标签