COGS——T 886. [USACO 4.2] 完美的牛栏
2024-10-01 13:34:06
http://www.cogs.pro/cogs/problem/problem.php?pid=886
★★☆ 输入文件:stall4.in
输出文件:stall4.out
简单对比
时间限制:1 s 内存限制:128 MB
- USACO/stall4(译by Felicia Crazy)
描述
农夫约翰上个星期刚刚建好了他的新牛棚,他使用了最新的挤奶技术。不幸的是,由于工程问题,每个牛栏都不一样。第一个星期,农夫约翰随便地让奶牛们进入牛栏,但是问题很快地显露出来:每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期,农夫约翰刚刚收集到了奶牛们的爱好的信息(每头奶牛喜欢在哪些牛栏产奶)。一个牛栏只能容纳一头奶牛,当然,一头奶牛只能在一个牛栏中产奶。
给出奶牛们的爱好的信息,计算最大分配方案。
格式
PROGRAM NAME: stall4
INPUT FORMAT:
(file stall4.in)
第一行 | 两个整数,N (0 <= N <= 200)和M (0 <= M <= 200)。N是农夫约翰的奶牛数量,M是新牛棚的牛栏数量。 |
第二行到第N+1行 |
一共N行,每行对应一只奶牛。第一个数字(Si)是这头奶牛愿意在其中产奶的牛栏的数目(0 <= Si<= M)。后面的Si个数表示这些牛栏的编号。牛栏的编号限定在区间(1..M)中,在同一行,一个牛栏不会被列出两次。 |
OUTPUT FORMAT:
(file stall4.out)
只有一行。输出一个整数,表示最多能分配到的牛栏的数量。
SAMPLE INPUT (file stall4.in)
5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2
SAMPLE OUTPUT (file stall4.out)
- 4
二分图最大匹配、、
#include <cstring>
#include <cstdio> const int N();
int n,m,ans;
bool vis[N];
int match[N],map[N][N]; bool find(int u)
{
for(int v=;v<=m;v++)
if(!vis[v]&&map[u][v])
{
vis[v]=;
if(!match[v]||find(match[v]))
{
match[v]=u;
return ;
}
}
return ;
} inline void read(int &x)
{
x=; register char ch=getchar();
for(;ch>''||ch<'';) ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-'';
} int AC()
{
freopen("stall4.in","r",stdin);
freopen("stall4.out","w",stdout); read(n),read(m);
for(int k,u=;u<=n;u++)
{
read(k);
for(int v;k--;)
read(v),map[u][v]=;
}
for(int i=;i<=n;i++)
{
if(find(i)) ans++;
memset(vis,,sizeof(vis));
}
printf("%d\n",ans);
return ;
} int Hope=AC();
int main(){;}
最新文章
- 把生成的excel文件直接提供为下载页效果
- SVN版本控制与分支设置
- java 类加载顺序
- freemarker中的round、floor和ceiling数字的舍入处理
- sql service重置自动增长字段数字的方法
- Radar Installation(POJ 1328 区间贪心)
- JavaScript-打开新窗口
- SQLite中如何用api操作BLOB类型的字段
- Vim插件管理 -- Vundle
- AKKA学习笔记
- Python读入CIFAR-10数据库
- thinkphp 面向切面编程-行为拓展
- MySQL实现阶段累加的sql写法 ,eq:统计余额
- nested exception is java.lang.ClassNotFoundException
- python--yield and generator(生成器)简述
- 手机APP UI设计尺寸基础知识
- JS 获取浏览器的宽和高
- cogs791 [HAOI2012] 音量调节
- Extjs gridPanel 动态指定表头
- eclipse的最新版本luna的中建立svn和maven
热门文章
- nodejs-配置vs code的插件
- [Linux]第四部分-Linux用户管理
- Spring进阶之路(10)-Advice简单介绍以及通过cglib生成AOP代理对象
- CDH使用秘籍(一):Cloudera Manager和Managed Service的数据库
- Codeforces Beta Round #29 (Div. 2, Codeforces format) C. Mail Stamps 拓扑排序
- File and Folder Permissions
- spring-boot系列:(一)整合dubbo
- javascript中封装scoll()方法
- X Macro
- 路飞学城Python-Day33