POJ 1274 The Perfect Stall(二分图最大匹配)
2024-09-06 15:48:44
题意:
N头牛M个牛棚,每只牛都有它自己指定的若干个它愿意呆的牛棚。
每个牛棚最多呆一头牛。
问最多可以满足多少头牛的愿望。
思路:
裸二分图最大匹配。
代码:
int n,m;
vector<int> graph[205];
int cx[205],cy[205];
bool bmask[205]; int findPath(int u){
int L=graph[u].size();
rep(i,0,L-1){
int v=graph[u][i];
if(!bmask[v]){
bmask[v]=true;
if(cy[v]==-1||findPath(cy[v])){
cy[v]=u;
cx[u]=v;
return 1;
}
}
}
return 0;
}
int MaxMatch(){
int ans=0;
rep(i,1,n) cx[i]=-1;
rep(i,1,m) cy[i]=-1;
rep(i,1,n) if(cx[i]==-1){
mem(bmask,false);
ans+=findPath(i);
}
return ans;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
rep(i,1,n) graph[i].clear();
rep(i,1,n){
int x,tx;
scanf("%d",&x);
while(x--){
scanf("%d",&tx);
graph[i].push_back(tx);
}
}
int dd=MaxMatch();
printf("%d\n",dd);
}
}
最新文章
- 463. Island Perimeter
- TextMate 通用快捷键
- 多级反向代理下,Java获取请求客户端的真实IP地址多中方法整合
- [转](二)unity4.6Ugui中文教程文档-------概要-UGUI Canvas
- Django开发博客- 三部曲
- 2013年7月份第2周51Aspx源码发布详情
- mysql记录sql执行时间
- zoj 3057 博弈
- rmi 与 远程代理复习
- HDOJ--4786--Fibonacci Tree【生成树】
- Ecstore中如何调用发起Ajax请求
- SilkTest高级进阶系列6-motif tag
- POJ2411 Mondriaan&#39;s Dream(状态压缩)
- HTML5可以省略全部标记的元素
- 权限的控制 shiro的使用
- 能ping通虚拟机,但snmp报文 Destination unreachable(Host administratively prohibited
- ubuntu 下安装 navicat 12
- swal() 弹出层的用法
- Linux编程 5 (目录重命名与移动mv,删除文件rm,目录创建mkdir删除rmdir,查看file,cat,more,tail,head)
- 【vue】vue的路由权限管理
热门文章
- VSCode Remote-SSH 连接服务器
- Elasticsearch(ES)集群的搭建
- cmake入门:01 构建一个简单的可执行程序
- 定要过python二级 第10套
- NWERC2020J-Joint Excavation【构造,贪心】
- P4351-[CERC2015]Frightful Formula【组合数学,MTT】
- P2179-[NOI2012]骑行川藏【导数,二分】
- 淘宝商品html--网页结构
- 启用 Spring-Cloud-OpenFeign 配置可刷新,项目无法启动,我 TM 人傻了(上)
- HTML常用的css属性(及其简写)