Codeforces Gym 104059B - Breeding Bugs

简要题意

给出一个长度为 \(n\) 的序列 \(a\)，你需要从中选出一些数，使其两两相加不为质数。输出最大可以选择多少个数。

\(1 \leq n \lt 750,1 \leq a_i \lt 10^7\)

思路

Imakf 学长推荐的题。

首先我们发现，如果对于任意两个数 \(a_i,a_j\)，如果 \((a_i+a_j)\in\mathbb{P}\)，连边 \((i,j)\)。然后答案就是图的最大独立集。但是一般图最大独立集是 NP-Complete 问题，目前没有多项式时间复杂度解法。

考虑到若 \(a_i,a_j\neq 1\)，那么若 \((a_i+a_j)\in\mathbb{P}\)，则 \(a_i\bmod 2\neq b_i\bmod 2\)。则若满足上述条件连边，就一定得到的是二分图。

好，然后跑二分图最大匹配，最后将二分图最大匹配转换成二分图最大独立集即可。

等一下，\(a_i=a_j=1\) 的问题我们没有解决，由于如果独立集中有两个及以上 \(1\) 就一定会有质数和出现（\(1+1=2,2\in\mathbb{P}\)），所以我们对值为 \(1\) 的 \(a_i\) 去重即可。

使用匈牙利算法求解二分图最大匹配，时间复杂度均摊 \(O(\max a+n\cdot\frac{n^2}{\log n})\)（这个复杂度是我用素数定理乱算的），理论复杂度上界 \(O(\max a+n^3)\)。可以通过本题。

（思路不难，细节贼多）

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

int pri[20000005];

bool vis[20000005];

int tot;

int n,p[800];

struct edge{

    int nxt,to;

} g[10000005];

int head[800],ec;

void add(int u,int v){

    g[++ec].nxt=head[u];

    g[ec].to=v;

    head[u]=ec;

}

int vist[800],mch[800];

bool hungry(int u,int tag){

    if(vist[u]==tag) return false;

    vist[u]=tag;

    for(int i=head[u];i;i=g[i].nxt){

        int v=g[i].to;

        if(mch[v]==0||hungry(mch[v],tag)){

            mch[v]=u;

            return true;

        }

    }

    return false;

}

signed main(){

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>n;

    vis[1]=1;vis[0]=1;

	for(int i=2;i<=(2e7);i++){

		if(!vis[i]){

			pri[++tot]=i;

		}

		for(int j=1;j<=tot&&i*pri[j]<=(2e7);j++){

			vis[i*pri[j]]=1;

			if(!(i%pri[j]))break;

		}

	}

    for(int i=1;i<=n;i++) cin>>p[i];

    sort(p+1,p+n+1, greater<int>());

    if(p[n]==1){

        while(p[n]==1) n--;

        n++;

    }

    for(int i=1;i<=n;i++){

        if(!(p[i]&1)) continue;

        for(int j=1;j<=n;j++){

            if((p[j]&1)) continue;

            if(!vis[p[i]+p[j]]) {

                add(i,j);

            }

        }

    }

    int ret=0;

    for(int i=1;i<=n;i++){

        if(hungry(i,i)) ret++;

    }

    cout<<(n-ret);

}

AC Record on Virtual Judge | Codeforces Gym AC 记录 ID：\(188853866\)

巴特西

Codeforces Gym 104059B - Breeding Bugs

简要题意

思路

代码

最新文章

热门文章