博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
AC日记——【模板】二分图匹配 洛谷 P3386
阅读量:5860 次
发布时间:2019-06-19

本文共 2107 字,大约阅读时间需要 7 分钟。

题目背景

二分图

题目描述

给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数

输入输出格式

输入格式:

 

第一行,n,m,e

第二至e+1行,每行两个正整数u,v,表示u,v有一条连边

 

输出格式:

 

共一行,二分图最大匹配

 

输入输出样例

输入样例#1:
1 1 11 1
输出样例#1:
1

说明

n,m<=1000,1<=u<=n,1<=v<=m

因为数据有坑,可能会遇到v>m的情况。请把v>m的数据自觉过滤掉。

算法:二分图匹配

 

思路:

  二分图模板;

 

来,上代码:

#include 
#include
#include
#include
#include
#define maxn 1005#define INF 0x7fffffffusing namespace std;struct EdgeType { int v,f,e;};struct EdgeType edge[maxn*maxn*2];int cnt,deep[maxn<<1],ans,e;int n,m,head[maxn<<1],s=0,t=(maxn<<1)-1;char Cget;inline void in(int &now){ now=0,Cget=getchar(); while(Cget>'9'||Cget<'0') Cget=getchar(); while(Cget>='0'&&Cget<='9') { now=now*10+Cget-'0'; Cget=getchar(); }}bool bfs(){ for(int i=s;i<=t;i++) deep[i]=-1; queue
que;deep[s]=0,que.push(s); while(!que.empty()) { int now=que.front();que.pop(); for(int i=head[now];i;i=edge[i].e) { if(edge[i].f>0&&deep[edge[i].v]<0) { deep[edge[i].v]=deep[now]+1; if(edge[i].v==t) return true; que.push(edge[i].v); } } } return false;}int flowing(int now,int flow){ if(now==t||flow<=0) return flow; int oldflow=0; for(int i=head[now];i;i=edge[i].e) { if(edge[i].f<=0||deep[edge[i].v]!=deep[now]+1) continue; int pos=flowing(edge[i].v,min(edge[i].f,flow)); if(pos>0) { flow-=pos; oldflow+=pos; edge[i].f-=pos; edge[i^1].f+=pos; if(flow==0) return oldflow; } } if(oldflow==0) deep[now]=-1; return oldflow;}int main(){ in(n),in(m),in(e); for(int i=1;i<=n;i++) { edge[++cnt].v=i,edge[cnt].f=1,edge[cnt].e=head[s],head[s]=cnt; edge[++cnt].v=s,edge[cnt].f=0,edge[cnt].e=head[i],head[i]=cnt; } for(int i=1+n;i<=m+n;i++) { edge[++cnt].v=t,edge[cnt].f=1,edge[cnt].e=head[i],head[i]=cnt; edge[++cnt].v=i,edge[cnt].f=0,edge[cnt].e=head[t],head[t]=cnt; } int u,v; while(e--) { in(u),in(v);v+=n; edge[++cnt].v=v,edge[cnt].f=1,edge[cnt].e=head[u],head[u]=cnt; edge[++cnt].v=u,edge[cnt].f=0,edge[cnt].e=head[v],head[v]=cnt; } while(bfs()) ans+=flowing(s,INF); cout<

 

转载于:https://www.cnblogs.com/IUUUUUUUskyyy/p/6648368.html

你可能感兴趣的文章
轻松搞定RabbitMQ(六)——主题
查看>>
Mysql事物隔离级别
查看>>
redmine 安装过程中的无数坑
查看>>
windows 中使用 docker 运行 nginx
查看>>
ios摇一摇的实现
查看>>
Freemarker + XML 导出Word
查看>>
The Easiest Way to Find Free Vectors, Stock Pho...
查看>>
ThinkPHP3.2.3的函数汇总
查看>>
编译《Hadoop权威指南》中MaxTemperatureDriverTest,出现Match...
查看>>
solve "An error occurred while installing pg"
查看>>
带发光的表单
查看>>
Linux下安装使用Solr
查看>>
Mac使用Homebrew下安装git
查看>>
java中值传递的理解,C++中传值传递、引用传递和指针方式的理解
查看>>
linux设备驱动第三篇:写一个简单的字符设备驱动
查看>>
table-样式1
查看>>
springMVC笔记系列(12)——使用Servlet原生API的类型参数
查看>>
ubuntu13.04 有线网卡驱动安装 无法上网 网络配置
查看>>
xml格式说明文档
查看>>
Text
查看>>