LightOJ--1149--Factors and Multiples(二分图好题)
Time Limit: 2000MS | Memory Limit: 32768KB | 64bit IO Format: %lld & %llu |
Description
You will be given two sets of integers. Let's call them set A and set
B. Set A contains n elements and set
B contains m elements. You have to remove
k1 elements from set A and k2 elements from set
B so that of the remaining values no integer in set B is a multiple of any integer in set
A. k1 should be in the range
[0, n] and k2 in the range [0, m].
You have to find the value of (k1 + k2) such that
(k1 + k2) is as low as possible. P is a multiple of
Q if there is some integer K such that
P = K * Q.
Suppose set A is {2, 3, 4, 5} and set
B is {6, 7, 8, 9}. By removing 2 and
3 from A and 8 from B, we get the sets
{4, 5} and {6, 7, 9}. Here none of the integers
6, 7 or 9 is a multiple of 4 or
5.
So for this case the answer is 3 (two from set
A and one from set B).
Input
Input starts with an integer T (≤ 50), denoting the number of test cases.
The first line of each case starts with an integer n followed by
n positive integers. The second line starts with m followed by
m positive integers. Both n and m will be in the range
[1, 100]. Each element of the two sets will fit in a 32 bit signed integer.
Output
For each case of input, print the case number and the result.
Sample Input
2
4 2 3 4 5
4 6 7 8 9
3 100 200 300
1 150
Sample Output
Case 1: 3
Case 2: 0
Source
给了两个集合A,B,分别有n,m个数,从A取k1个数,B取k2个数,使得b[ j ]%a[ i ]==0的情况不存在
刚开始以为可以暴力的,但是后来发现暴力真的是挺麻烦,把图画出来之后会发现,其实就是最小点覆盖,二分图性质:最小点覆盖=最大匹配,匈牙利算法跑一次
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>map[200];
int used[200],pipei[200],a[200],b[200];
int n,m;
int find(int x)
{ for(int i=0;i<map[x].size();i++)
{
int y=map[x][i];
if(!used[y])
{
used[y]=1;
if(pipei[y]==-1||find(pipei[y]))
{
pipei[y]=x;
return 1;
}
}
}
return 0;
}
int main()
{
int t,k=1;
scanf("%d",&t);
while(t--)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(pipei,-1,sizeof(pipei));
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
map[i].clear();
}
scanf("%d",&m);
for(int i=0;i<m;i++)
scanf("%d",&b[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(b[j]%a[i]==0)
{
map[i].push_back(j);
}
}
}
int sum=0;
for(int i=0;i<n;i++)
{
memset(used,0,sizeof(used));
sum+=find(i);
}
printf("Case %d: %d\n",k++,sum);
}
return 0;
}
最新文章
- 如何在一个页面添加多个不同的kindeditor编辑器
- Oracle Data Provider for .NET
- String 两种实例化方式的区别
- dotNet中初始化器的使用
- Java中的10颗语法糖
- php中的preg系列函数
- 关于mysql的自增
- ssh三大框架,三层架构 整合测试!完整分页代码,JdbcTemplate等测试,存储过程调用,留着以后复习吧
- linux面试题集锦2《转》
- 一行code实现ADO.NET查询结果映射至实体对象。
- Javaweb项目碰到的问题- Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password: YES)
- c语言static关键字的理解
- freebsd 时间校准
- hdu多校第4场 B Harvest of Apples(莫队)
- SPOJ GSS3 (动态dp)
- vue的watcher 关于数组和对象
- 35_张孝祥Java高新技术_为注解增加各种属性
- 淡淡理解下AngularJS中的module
- C中预编译详解
- iptables-save和iptables-restore