Description
A set of integers is called prime independent if none of its member is a prime multiple of another member. An integera is said to be a prime multiple of b if,
a = b x k (where k is a prime [1])
So, 6 is a prime multiple of 2, but 8 is not. And for example, {2, 8, 17} is prime independent but {2, 8, 16} or {3, 6} are not.
Now, given a set of distinct positive integers, calculate the largest prime independent subset.
Input
Input starts with an integer T (≤ 20), denoting the number of test cases.
Each case starts with an integer N (1 ≤ N ≤ 40000) denoting the size of the set. Next line contains N integers separated by a single space. Each of these N integers are distinct and between 1 and 500000 inclusive.
Output
For each case, print the case number and the size of the largest prime independent subset.
Sample Input
3
5
2 4 8 16 32
5
2 3 4 6 9
3
1 2 3
Sample Output
Case 1: 3
Case 2: 3
Case 3: 2
題意：
給出n個數，找出一個最大素數獨立子集，如果a=b*一個素數，那麼認為a是b的一個素數乘級，如果一個集合不存在一個數是另一個數的素數乘級，那麼這就是素數獨立子集。
思路：
很像最大獨立集，但是這是NP問題，想是否能轉化為二分圖。
建圖思路，每個數要麼是奇數個素數的乘級，要麼是偶數個，奇數和奇數之間不會有聯系，根據這點性質將圖劃分為二分圖，剩下的就是二分圖算法了，此題時間卡的緊，必須要用高級一點的二分圖算法。
代碼：
#include#include #include #define maxn 40005 using namespace std; int ans,n,m,num,cnt; bool app[500005]; int vis[500005],pri[50000],ha[500005]; int a[maxn],head[maxn]; int sta[maxn],top; bool use[maxn]; int nx,ny; int cx[maxn],cy[maxn];// cx[i]表示xi對應的匹配 cy[i]表示yi對應的匹配 int distx[maxn],disty[maxn]; // bfs中的第幾層 int que[maxn*20]; struct node { int v,next; }edge[maxn*20]; void addedge(int u,int v) { cnt++; edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt; } void sieze() { int i,j; memset(app,0,sizeof(app)); for(i=2;i<=500000;i++) { if((long long)i*i>=500000) break ; if(!app[i]) for(j=i*i;j<=500000;j+=i) { app[j]=1; } } num=0; for(i=2;i<=500000;i++) { if(app[i]==0) pri[++num]=i; } memset(ha,0,sizeof(ha)); int res; for(i=2;i<=500000;i++) { int x=i; res=0; for(j=1;j<=num&&j*j<=x;j++) { while(x%pri[j]==0) { x/=pri[j]; res++; } } if(x!=1) res++; ha[i]=res&1; } //printf("%d\n",num); } void init() { memset(cx,-1,sizeof(cx)); memset(cy,-1,sizeof(cy)); memset(head,-1,sizeof(head)); } bool bfs() { int i,j,k,u,v,h,t; bool flag=0; memset(distx,0,sizeof(distx)); memset(disty,0,sizeof(disty)); t=0; for(i=1; i<=nx; i++) { if(cx[i]==-1) que[t++]=i; } for(h=0 ; h!=t; h++) { u=que[h]; for(k=head[u]; k!=-1; k=edge[k].next) { v=edge[k].v; if(!disty[v]) { disty[v]=distx[u]+1; if(cy[v]==-1) flag=1; else distx[cy[v]]=disty[v]+1,que[t++]=cy[v]; } } } return flag; } bool dfs(int i) { int j,k; for(k=head[i]; k!=-1; k=edge[k].next) { j=edge[k].v; if(disty[j]==distx[i]+1) // 說明j是i的後繼結點 { disty[j]=0; // j被用過了 不能再作為其他點的後繼結點了 if(cy[j]==-1||dfs(cy[j])) { cx[i]=j,cy[j]=i; return 1; } } } return 0; } void Hopcroft_Karp() { int i,j; ans=0; while(bfs()) { for(i=1; i<=nx; i++) { if(cx[i]==-1 && dfs(i)) ans++; } } } void solve() { int i,j; int u,v; init(); cnt=0; for(i=1;i<=n;i++) { for(j=1;j<=num;j++) { if(a[i]*pri[j]>500000) break ; v=a[i]*pri[j]; if(vis[v]) { addedge(vis[a[i]],vis[v]); addedge(vis[v],vis[a[i]]); } } } Hopcroft_Karp(); } int main() { int i,j,t,ca=0; sieze(); scanf("%d",&t); while(t--) { scanf("%d",&n); int tmp=0; memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) { scanf("%d",&a[i]); if(ha[a[i]]) vis[a[i]]=++tmp; } nx=tmp; ny=n-tmp; for(i=1;i<=n;i++) { if(!ha[a[i]]) vis[a[i]]=++tmp; } solve(); printf("Case %d: %d\n",++ca,n-ans); } return 0; }
