题意:

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);
}
}

最新文章

  1. 463. Island Perimeter
  2. TextMate 通用快捷键
  3. 多级反向代理下,Java获取请求客户端的真实IP地址多中方法整合
  4. [转](二)unity4.6Ugui中文教程文档-------概要-UGUI Canvas
  5. Django开发博客- 三部曲
  6. 2013年7月份第2周51Aspx源码发布详情
  7. mysql记录sql执行时间
  8. zoj 3057 博弈
  9. rmi 与 远程代理复习
  10. HDOJ--4786--Fibonacci Tree【生成树】
  11. Ecstore中如何调用发起Ajax请求
  12. SilkTest高级进阶系列6-motif tag
  13. POJ2411 Mondriaan&#39;s Dream(状态压缩)
  14. HTML5可以省略全部标记的元素
  15. 权限的控制 shiro的使用
  16. 能ping通虚拟机,但snmp报文 Destination unreachable(Host administratively prohibited
  17. ubuntu 下安装 navicat 12
  18. swal() 弹出层的用法
  19. Linux编程 5 (目录重命名与移动mv,删除文件rm,目录创建mkdir删除rmdir,查看file,cat,more,tail,head)
  20. 【vue】vue的路由权限管理

热门文章

  1. VSCode Remote-SSH 连接服务器
  2. Elasticsearch(ES)集群的搭建
  3. cmake入门:01 构建一个简单的可执行程序
  4. 定要过python二级 第10套
  5. NWERC2020J-Joint Excavation【构造,贪心】
  6. P4351-[CERC2015]Frightful Formula【组合数学,MTT】
  7. P2179-[NOI2012]骑行川藏【导数,二分】
  8. 淘宝商品html--网页结构
  9. 启用 Spring-Cloud-OpenFeign 配置可刷新,项目无法启动,我 TM 人傻了(上)
  10. HTML常用的css属性(及其简写)