LightOJ - 1356 Prime Independence (数论+二分图匹配)

题意：有N个数的集合，其中选出若干个数组成一个子集，要求这个子集中的任意两个数a,b都不能通过a=k*b得到，其中k是一个素数。求这个子集最大的size。

分析：集合中任意两数的关系是二者之间是否之差一个质因子，那么对于这种关系，本题要求的是N个点的最大独立集。|最大独立集| = 点数 - |二分图最大匹配|。

想到这步之后，就是如何建图的问题。

先预处理筛出一定范围内的素数。对于每个集合内的数a，检查其除去一个质因子后得到的数at是否在集合中出现，若出现则将a到at和at到a建边。

因为是双向建边，所以得到的最大匹配数是两倍，除以2即可。

    #include<bits/stdc++.h>

    using namespace std;

    typedef long long LL;

    const int MAXN = ;

    const int MAXM = *;

    const int INF = 0x3f3f3f3f;

    int N;

    struct Node{

        int x,y;

    }p[MAXN],it[MAXN];

    int v[MAXN];

    struct Edge{

        int v;

        int next;

    }edge[MAXM];

    int nx, ny;

    int cnt;

    int t;

    int dis;

    int first[MAXN];

    int xlink[MAXN], ylink[MAXN];

    /*xlink[i]表示左集合顶点所匹配的右集合顶点序号，ylink[i]表示右集合i顶点匹配到的左集合顶点序号。*/

    int dx[MAXN], dy[MAXN];

    /*dx[i]表示左集合i顶点的距离编号，dy[i]表示右集合i顶点的距离编号*/

    int vis[MAXN]; //寻找增广路的标记数组

    void init(){

        cnt = ;

        memset(first, -, sizeof(first));

        memset(xlink, -, sizeof(xlink));

        memset(ylink, -, sizeof(ylink));

    }

    void AddEdge(int u, int v){

        edge[cnt].v = v;

        edge[cnt].next = first[u], first[u] = cnt++;

    }

    int bfs()

    {

        queue<int> q;

        dis = INF;

        memset(dx, -, sizeof(dx));

        memset(dy, -, sizeof(dy));

        for(int i = ; i <= nx; i++){

            if(xlink[i] == -){

                q.push(i);

                dx[i] = ;

            }

        }

        while(!q.empty()){

            int u = q.front(); q.pop();

            if(dx[u] > dis) break;

            for(int e = first[u]; e != -; e = edge[e].next){

                int v = edge[e].v;

                if(dy[v] == -){

                    dy[v] = dx[u] + ;

                    if(ylink[v] == -) dis = dy[v];

                    else{

                        dx[ylink[v]] = dy[v]+;

                        q.push(ylink[v]);

                    }

                }

            }

        }

        return dis != INF;

    }

    int find(int u){

        for(int e = first[u]; e != -; e = edge[e].next){

            int v = edge[e].v;

            if(!vis[v] && dy[v] == dx[u]+){

                vis[v] = ;

                if(ylink[v] != - && dy[v] == dis) continue;

                if(ylink[v] == - || find(ylink[v])){

                    xlink[u] = v, ylink[v] = u;

                    return ;

                }

            }

        }

        return ;

    }

    int MaxMatch()

    {

        int ans = ;

        while(bfs()){

            memset(vis, , sizeof(vis));

            for(int i = ; i <= nx; i++)

                if(xlink[i] == -)

                    ans += find(i);

        }

        return ans;

    }

    const int MAXV = ;

    int prime[MAXV];

    bool notprime[MAXV*];

    void pre()

    {

        int up  = MAXV *;

        memset(notprime,,sizeof(notprime));

        notprime[] = notprime[] = true;

        memset(prime,,sizeof(prime));

        for(int i=;i<up;++i){

            if(!notprime[i]) prime[++prime[]] = i;

            for(int j= ; j<=prime[] && prime[j] <= up / i ;++j){

                notprime[prime[j]*i] = true;

                if(i%prime[j]==) break;

            }

        }

    }

    int pos[MAXV*];

    int num[MAXV];

    int fac[MAXV];

    bool jo[MAXV*];

    void ADD(int num,int pt){

        int sum = ,all=;

        int tmp = num;

        for(int i=;prime[i]*prime[i]<=tmp;i++){

            if(tmp%prime[i]==){

                fac[sum++] = prime[i];

                while(tmp%prime[i]==) tmp/=prime[i],all++;

            }

        }

        if(tmp>) fac[sum++] = tmp,all++;

        for(int i=;i<sum;++i){

            int x = num/fac[i];

            if(pos[x]){

                AddEdge(pt,pos[x]);

                AddEdge(pos[x],pt);

            }

        }

    }

    int main()

    {

        #ifndef ONLINE_JUDGE

            freopen("in.txt","r",stdin);

            freopen("out.txt","w",stdout);

        #endif

        pre();

        int T,cas=; scanf("%d",&T);

        while(T--){

            int N; scanf("%d",&N);

            init();

            memset(pos,,sizeof(pos));

            for(int i=;i<=N;++i){

                scanf("%d",&num[i]);

                pos[num[i]] = i;

            }

            nx = ny =;

            for(int i=;i<=N;++i){

                ADD(num[i],i);

            }

            nx = ny = N;

            int res= N - MaxMatch()/;

            printf("Case %d: %d\n",cas++,res);

        }

        return ;

    }

巴特西

LightOJ - 1356 Prime Independence (数论+二分图匹配)

最新文章

热门文章