light oj 1149 Factors and Multiples(二分匹配)

LightOJ1149 :Factors and Multiples

时间限制:2000MS 内存限制:32768KByte 64位IO格式:%lld & %llu

描述

You will be given two sets of integers. Let's call them set Aand set B. Set A contains n elements and set Bcontains m elements. You have to remove k₁ elements from set A and k₂ elements from set B so that of the remaining values no integer in set B is a multiple of any integer in set A. k₁ should be in the range [0, n] and k₂in the range [0, m].

You have to find the value of (k₁ + k₂)such that (k₁ + k₂) is as low as possible. Pis 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 Bis {6, 7, 8, 9}. By removing 2 and 3 from A and 8from 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 setA and one from set B).

输入

Input starts with an integer T (≤ 50), denoting the number of test cases.

The first line of each case starts with an integer nfollowed by n positive integers. The second line starts with mfollowed 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 32bit signed integer.

输出

For each case of input, print the case number and the result.

样例输入

2

4 2 3 4 5

4 6 7 8 9

3 100 200 300

1 150

样例输出

Case 1: 3

Case 2: 0

提示

题目来源

Problem Setter: Sohel Hafiz

Special Thanks: Jane Alam Jan

唉...已经不想说话了...后续再补...

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <math.h>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <climits>
 8 #include <queue>
 9 #define ll long long
10 
11 using namespace std;
12 
13 const int N = 20000;
14 int head[N],total,visit[N];
15 int link[N];
16 
17 struct nodes
18 {
19     int e,next;
20 } Edge[N];
21 
22 
23 void add(int x,int y)
24 {
25     Edge[total].e = y;
26     Edge[total].next = head[x];
27     head[x] = total++;
28 }
29 
30 int dfs(int f)
31 {
32     for(int i  = head[f]; i != -1; i = Edge[i].next)
33     {
34         int s = Edge[i].e; 
35         if(visit[s]) continue;
36         visit[s] = 1;
37         if(link[s] == -1 || dfs(link[s]))
38         {
39             link[s] = f ;
40             return 1;
41         }
42     }
43     return 0;
44 }
45 
46 void init()
47 {
48     total = 0;
49     memset(head,-1,sizeof(head));
50     memset(link,-1,sizeof(link));
51 }
52 
53 int main(void)
54 {
55     int t,a[105],b[105];
56     int i,j,cnt1 = 1;
57     cin>>t;
58     while(t--)
59     {
60         init();
61         int m,n;
62         cin>>m;
63         for(i = 0; i < m; i++)
64         {
65             scanf("%d",&a[i]);
66         }
67         cin>>n;
68         for(i = 0; i < n; i++)
69         {
70             scanf("%d",&b[i]);
71         }
72         for(i = 0; i < m; i++)
73             for(j = 0; j < n; j++)
74                 if(b[j] % a[i] == 0)
75                 add(i,m+j);
76         int cnt;
77         for(cnt = 0,i = 0; i < m+n; i++)
78         {
79             memset(visit,0,sizeof(visit));
80             if(dfs(i))
81                 cnt++;
82         }
83         printf("Case %d: %d
",cnt1++,cnt);
84     }
85 
86     return 0;
87 }