题目链接：
http://lightoj.com/volume_showproblem.php?problem=1149
1149 - Factors and Multiples
PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB 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. k1should 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
Output for Sample Input
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
//
题目大意：
集合A中有N个数，集合B中有M个数，现在需要在A集合中去掉K1个数，在B集合中去掉K2个数，现在需要（K1+K2）尽可能的小，保证剩余部分中,B集合中的任意数都不能整除A集合中的任意数。
对于B[i]%A[i]==0的两个建连接，然后求最大二分匹配==最小点覆盖==最大二分匹配数。
This is the code :
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define PI acos(-1.0)
#define EPS 1e-8
#define LL long long
#define ULL unsigned long long //1844674407370955161
#define INT_INF 0x3f3f3f3f //1061109567
#define LL_INF 0x3f3f3f3f3f3f3f3f //4557430888798830399
// ios::sync_with_stdio(false);
// 那么cin, 就不能跟C的 scanf，sscanf, getchar, fgets之类的一起使用了。inline int read()//输入外挂
{int ret=0, flag=0;char ch;if((ch=getchar())=='-')flag=1;else if(ch>='0'&&ch<='9')ret = ch - '0';while((ch=getchar())>='0'&&ch<='9')ret=ret*10+(ch-'0');return flag ? -ret : ret;
}struct Max_Match
{int p,q; //左右两点集的点个数vector<int> g[110]; //邻接矩阵,g[i]中保存的是左边第i个节点所连的右边节点的编号int left[310]; //left[i]==j表右边第i个点与左边第j个点匹配,为-1表无点匹配bool vis[310]; //表右边第i个点是否已经被访问过void init(int p,int q){this->p=p;this->q=q;for(int i=0; i<=p; i++)g[i].clear();memset(left,-1,sizeof(left));}bool match(int u){for(int j=0; j<g[u].size(); j++){int v=g[u][j];if(!vis[v]){vis[v]=true;if(left[v]==-1 || match(left[v]) ){left[v]=u;//此步相当于将增广路取反return true;}}}return false;}void solve(){int ans=0;//记录匹配边数for(int i=1; i<=p; i++){memset(vis,0,sizeof(vis));if(match(i))ans++;}printf("%d\n",ans);}
} MM;int a[105];
int b[105];int main()
{int T=read();for(int t=1;t<=T;++t){int p=read();for(int i=1;i<=p;++i)a[i]=read();int q=read();MM.init(q,p); //注意哪个变量是左边集合for(int i=1;i<=q;++i){b[i]=read();for(int j=1;j<=p;++j){if(b[i]%a[j]==0)MM.g[i].push_back(j);}}printf("Case %d: ",t);MM.solve();}return 0;
}