题目3 : 质数相关
时间限制:2000ms
单点时限:1000ms
内存限制:256MB
描述
两个数a和 b (a<b)被称为质数相关，是指a × p = b，这里p是一个质数。一个集合S被称为质数相关，是指S中存在两个质数相关的数，否则称S为质数无关。如{2, 8, 17}质数无关，但{2, 8, 16}, {3, 6}质数相关。现在给定一个集合S，问S的所有质数无关子集中，最大的子集的大小。
输入
第一行为一个数T，为数据组数。之后每组数据包含两行。
第一行为N，为集合S的大小。第二行为N个整数，表示集合内的数。
输出
对于每组数据输出一行，形如"Case #X: Y"。X为数据编号，从1开始，Y为最大的子集的大小。
数据范围
1 ≤ T ≤ 20
集合S内的数两两不同且范围在1到500000之间。
小数据
1 ≤ N ≤ 15
大数据
1 ≤ N ≤ 1000
- 样例输入
-
3
5
2 4 8 16 32
5
2 3 4 6 9
3
1 2 3 - 样例输出
-
Case #1: 3
Case #2: 3
Case #3: 2 好像是LOJ的原题，- -
二分匹配求最大独立集。#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define N 1010
#define M 500000 int n,m,k;
int a[N];
int vis[N];
int match[N];
int mpt[N][N]; int tot;
bool isprime[M+];
int prime[M+];
void init()
{
tot=;
memset(isprime,true,sizeof(isprime));
isprime[]=isprime[]=false;
for(int i=;i<=M;i++)
{
if(isprime[i]) prime[tot++]=i;
for(int j=;j<tot;j++)
{
if((ll)i*prime[j]>M) break;
isprime[i*prime[j]]=false;
if(i%prime[j]==)
break;
}
}
}
int dfs(int u)
{
for(int j=;j<=n;j++)
{
if(!vis[j] && mpt[u][j])
{
vis[j]=;
if(match[j]==- || dfs(match[j]))
{
match[j]=u;
return ;
}
}
}
return ;
}
bool judge(int a,int b)
{
if(a>b) swap(a,b);
if(b%a) return ;
int k=b/a;
if(isprime[k]) return ;
return ;
}
int main()
{
init();
int T,iCase=;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(mpt,,sizeof(mpt));
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++)
{
for(int j=i+;j<=n;j++)
{
if(judge(a[i],a[j]))
{
mpt[i][j]=;
mpt[j][i]=;
}
}
}
printf("Case #%d: ",iCase++);
int ans=;
memset(match,-,sizeof(match));
for(int i=;i<=n;i++)
{
memset(vis,,sizeof(vis));
if(dfs(i)) ans++;
}
printf("%d\n",n-ans/);
}
return ;
}