The Perfect Stall
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 17260 | Accepted: 7878 |
Description
Farmer John completed his new barn just last week, complete with all the latest milking technology. Unfortunately, due to engineering problems, all the stalls in the new barn are different. For the first week, Farmer John randomly assigned cows to stalls, but it quickly became clear that any given cow was only willing to produce milk in certain stalls. For the last week, Farmer John has been collecting data on which cows are willing to produce milk in which stalls. A stall may be only assigned to one cow, and, of course, a cow may be only assigned to one stall.
Given the preferences of the cows, compute the maximum number of milk-producing assignments of cows to stalls that is possible.
Given the preferences of the cows, compute the maximum number of milk-producing assignments of cows to stalls that is possible.
Input
The input includes several cases. For each case, the first line contains two integers, N (0 <= N <= 200) and M (0 <= M <= 200). N is the number of cows that Farmer John has and M is the number of stalls in the new barn. Each of the following N lines corresponds to a single cow. The first integer (Si) on the line is the number of stalls that the cow is willing to produce milk in (0 <= Si <= M). The subsequent Si integers on that line are the stalls in which that cow is willing to produce milk. The stall numbers will be integers in the range (1..M), and no stall will be listed twice for a given cow.
Output
For each case, output a single line with a single integer, the maximum number of milk-producing stall assignments that can be made.
Sample Input
5 5 2 2 5 3 2 3 4 2 1 5 3 1 2 5 1 2
Sample Output
4
题意:
给出 N (0 ~ 200)头牛和 M (0 ~ 200)个地方。每头牛都有自己中意的地方,并且只会在自己中意的地方生产。后给出 这 N 头牛喜欢的地方,首先给出一个个数 T,后给出这 T 个地方。问如何匹配使最大数量的牛能够生产。
思路:
二分图最大匹配。匈牙利算法。
AC:
#include <cstdio> #include <string.h> using namespace std; int vn,un; int w[205][205]; int vis[205],linker[205]; bool dfs(int u) { for(int v = 1;v <= vn;v++) if(w[u][v] && !vis[v]) { vis[v] = 1; if(linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } return false; } int hungary() { int res = 0; memset(linker,-1,sizeof(linker)); for(int u = 1;u <= un;u++) { memset(vis,0,sizeof(vis)); if(dfs(u)) res++; } return res; } int main() { while(~scanf("%d%d",&un,&vn)) { memset(w,0,sizeof(w)); for(int i = 1;i <= un;i++) { int num; scanf("%d",&num); while(num--) { int ans; scanf("%d",&ans); w[i][ans] = 1; } } printf("%d\n",hungary()); } return 0; }
相关推荐
pku acm 1274 The Perfect Stall 代码 二分图的最大匹配的匈牙利算法 解题报告请访问:http://blog.csdn.net/china8848
The Rise & Stall of SNS
解:(1)若使用排空流水线策略,则对条件分支,有两个额外的stall,对无条件分支,有一个额外的stall: CPI = 1+20%*2+5%*1 = 1.33
步进电机反向电动势 无传感器失速检测算法:电流过零时反电动势测量、恒定关闭时间法、PWM周期计数法 DRV8889-Q1 Stall Detection Algorithm
DELL戴尔Sierra升级12.6重启卡住60秒kextd stall (60s):'appleACPICPU'已解决!遍历大师们方法,综合之,方法和附件如下: 1、升级Clover5120版本 2、kexts下10.12内容放到10.13下 3、Other里面增加Lilu.kext和...
the fully developed rotating stall are two stages of the same phenomenon. The growth rate of these disturbances was in accord with that predicted by current analytical models. The prestall waves were ...
S12HY and S12XHY Stepper Stall Detect
#app-stall app-stall是 bash 脚本,可用于安装文件中指定的应用程序列表。 ###Getting app-stall 克隆 app-stall 存储库。 使用这个命令 - $ git clone ...
==自述 在Stall上书写文字是针对公共浴室的评论应用程序,以便用户可以在需要时找到想要使用的浴室。 如果您不打算运行rake doc:app,请随意使用其他标记语言。
通过bus hound 来抓包分析发现 PC 发送set idle命令下去后,从设备没有响应,所以PC变为stall状态。通过分析源代码和HID协议,修补漏洞之后可以在任何电脑上枚举成功。里面有具体的参考文件及修改好的代码,有什么...
2021年小班英语教案范文IT‘STALL.pdf
这个是install4j的激活密钥,一起使用的
它将阻塞其周围上下文中的所有其他内容,直到设置完成标志:调用 done() 将上下文程序流恢复到正常的 asyc安装$ npm install stall用 var stall = require ( 'stall' )//template for a sleep functionvar sleep = ...
STM32在编译HID设备时,会出现INSTALL PID的问题,该文件描述了修改方法及可能出现的异常
- Changed the mechanism to check for the required DirectX Direct3D as the previous method did not work on some system (some W2003 servers). - Enhanced the mechanism to report memory hardware errors ...
1.理解流水线CPU的基本原理和组织结构 2.掌握五级流水线的工作过程和设计方法 3.理解流水线CPU停机的原理与解决办法 4.设计流水线测试程序 3. VIV
Stall Instagram下载器-Chrome插件,可让您从Instagram下载照片和视频。 Instagram试图阻止任何未经授权的用户内容下载,不允许您将Instagram照片和视频保存到本地PC。 Stall Instagram下载器的创建是为了绕过...
This specification only uses the default pipe to clear a STALL condition on the Bulk endpoints and to issue class-specific requests as defined below. This specification does not require the use...
| | 能级转换 这是Minecraft 1.16及更高版本上的Minecraft Mod-能级转换的官方资料库 需要: 介绍 在制品 背景 ... ...具有“ -elt”开头的Mod-ID的该Mod的所有模块均已获得GNU通用公共许可证版本3的许可。...
本地pip安装seaborn包,本地pip安装seaborn包,本地pip安装seaborn包,本地pip安装seaborn包,本地pip安装seaborn包,本地pip安装seaborn包,本地pip安装seaborn包,本地pip安装seaborn包,本地pip安装seaborn包,...