程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LightOJ 1356 Prime Independence (素數 二分圖)

LightOJ 1356 Prime Independence (素數 二分圖)

編輯:C++入門知識

LightOJ 1356 Prime Independence (素數 二分圖)


Prime Independence Time Limit:3000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu Submit Status Practice LightOJ 1356

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;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved