博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 1274 二分图匹配
阅读量:6717 次
发布时间:2019-06-25

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

匈牙利算法 裸题

//By SiriusRen#include 
#include
#include
using namespace std;int n,p[8085],first[8888],next[8888],v[8888],tot,vis[8888],m,xx,yy,ans;void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}bool dfs(int x){ for(int i=first[x];~i;i=next[i]){ if(!vis[v[i]]){ vis[v[i]]=1; if(!p[v[i]]||dfs(p[v[i]])){ p[v[i]]=x; return 1; } } } return 0;}int main(){ while(~scanf("%d%d",&n,&m)){ memset(p,0,sizeof(p)); memset(first,-1,sizeof(first)),ans=tot=0; for(int i=1;i<=n;i++){ scanf("%d",&xx); while(xx--){ scanf("%d",&yy); add(i,200+yy),add(200+yy,i); } } for(int i=1;i<=n;i++){ if(!p[i]){ memset(vis,0,sizeof(vis)); if(dfs(i))ans++; } } printf("%d\n",ans); }}

转载于:https://www.cnblogs.com/SiriusRen/p/6532291.html

你可能感兴趣的文章
李清照曹雪芹“躺枪”,古风歌真的都是词藻堆砌吗?
查看>>
BAT互联网公司的程序员,应用程序架构思路,这些都懂?
查看>>
台湾知名炸鸡连锁店疑供应逾期肉品 遭封存追查
查看>>
澳门2018年入境旅客3580万人次 创记录新高
查看>>
甘肃祁连山加大生态保护 北麓草原冬日现绿头鸭
查看>>
公务员周末送外卖是否违纪?官方暖心回复获网友点赞
查看>>
双星闪耀 上汽大众途岳、全新一代帕萨特联袂亮相
查看>>
监控系统云计算核心技术,主要包括十项技术
查看>>
下半年最值得关注的10个技术公众号
查看>>
MySQL 异步驱动浅析 (一):性能分析
查看>>
理解高性能网络模型
查看>>
提高 JavaScript 开发效率的高级 VSCode 扩展!
查看>>
30岁的你,还在写代码吗?
查看>>
阿里提出联合预估算法JUMP:点击率和停留时长预测效果最优
查看>>
世界杯要来了,AI预测冠军哪家强?
查看>>
代码这样写更优雅 (Python 版)
查看>>
SVG入门—如何手写SVG
查看>>
【面试必备】透过源码角度一步一步带你分析 ArrayList 扩容机制
查看>>
深入理解虚拟机之虚拟机性能监控和故障处理工具
查看>>
写个 vue-loading-template 组件
查看>>