题意

给n个数字（偶数个），找出尽量多组（每组恰好2个），让每组的数的和都为质数。求最大组数

限制：每个数字最多属于其中一个组，每个值在$[2,30000][2,30000]$[2,30000] 之间，n不大于100

方法

增广路径

首先所有数都不小于2，因此，所有和为质数必定是奇质数，那么两个整数相加为奇数，必定一个奇一个偶。

所以我们把数分成奇偶两部分，如果某个偶数和某个奇数相加是质数，那么我们建立一条从该偶数指向该奇数的边

实际要求的是，最大的可选边，且每个点至多属于一条边。

这样抽象后，就是一个典型的二分图最大匹配/网络流问题

以样例数据为例

首先我们给网络增加源点和汇点，并和现有的奇偶点相连，所有边的度都是1

注意到这里，凡是源和汇的边的增广路径,在实际上都不会使用，所以我们去掉这些边，用额外标识表示一个奇数点是否走到，它是否和汇连接。每次我们需要找一条偶数出发，未标记的奇数结尾的简单路径即可。

第一次找到2->5, 于是把这条简单路径反向，且标记5已经和汇点相连，计数+1

第二次，虽然有6->5但是5被标记了，所以只有6->13可行, 同样标记13，反向简单路径，计数+1

所以最终答案为2

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,b) for (ll i=(a);i<(b);i++)
#define pb push_back

int n;

bool isprime(int v){ // 是否为素数
    rep(i,2,v){
        if(v%i == 0)return false;
    }
    return true;
}

// 传入 下标,原数组,本次dfs是否访问过vis, 可选路径，是否连接汇点，当前dfs上的点
bool dfs(int idx,const vector<int>&num,vector<bool>& vis, vector<vector<bool>> & path, vector<bool> & matched,vector<int> & ps){
  if(num[idx] % 2 && !matched[idx]){ // 找到出点
    matched[idx] = true; // 标记匹配
    // 反转ps中构成的边
    ps.pb(idx);
    rep(i,0,ll(ps.size())-1){
      path[ps[i]][ps[i+1]] = false;
      path[ps[i+1]][ps[i]] = true;
    }
    return true;
  }
  vis[idx] = true;
  ps.pb(idx); // 当前点加入
  rep(i,0,n){
    if(!path[idx][i])continue; // 有可选路径
    // 存在 idx -> i 的边
    if(vis[i])continue; // 未访问过
    bool r = dfs(i,num,vis,path,matched,ps);
    if(r)return r;
  }
  ps.pop_back(); // 当前点弹出
  return false;
}

int main(){
  while(~scanf("%d",&n)){
    vector<int> num;
    int v;
    rep(i,0,n){
      scanf("%d",&v); // 读入
      num.pb(v);
    }
    // 已连接汇点
    vector<bool> matched(n,false);
    // 可选路径
    vector<vector<bool> > path(n,vector<bool>(n,false));
    rep(i,0,n){
      if(num[i]%2)continue; // 偶点
      rep(j,0,n){
        if(num[j]%2 == 0)continue; // 奇点
        if(!isprime(num[i]+num[j]))continue; // 是否为质数
        path[i][j] = true;
      }
    }
    int ans = 0;
    rep(i,0,n){
      if(num[i]%2)continue;
      vector<bool> vis(n,false);
      vector<int> ps = {};
      ans += dfs(i,num,vis,path,matched,ps); // 计数
    }
    printf("%d\n",ans);
  }
  return 0;
}

复杂度分析

时间复杂度: 前期初始化的复杂度，主要在建立边$O(n^2\cdot max(\sqrt{a_i}\left)\right)O(n^2\; \backslash cdot\; max(\backslash sqrt\{a\_i\}))$O(n2⋅max(ai​​)), 搜索过程中，每个偶数点触发一次dfs，一次dfs最坏情况，遍历所有边，所以搜索的过程中时间复杂度为$O\left(n^3\right)O(n^3)$O(n3), 总时间复杂度为$O\left(max\right(n^3,n^2\cdot max\left(\sqrt{a_i}\right)\left)\right)O(max(n^3,n^2\; \backslash cdot\; max(\backslash sqrt\{a\_i\})))$O(max(n3,n2⋅max(ai​​)))

空间复杂度: 空间分为两部分，

建立的访问数组，路径数组，标识数组等，最大的是路径数组为$O\left(n^2\right)O(n^2)$O(n2)

递归栈消耗，因为中间全部是引用传递，其余是常量个变量，所以仅与栈深度相关为$O\left(n\right)O(n)$O(n)

所以空间复杂度为$O\left(n^2\right)O(n^2)$O(n2)

质数表优化建边过程

注意到上面，建立边每次都会去$O\left(\sqrt{a_i}\right)O(\backslash sqrt\{a\_i\})$O(ai​​)的查询是否为质数，如果能提前建立质数表。那么每次就可以$O\left(1\right)O(1)$O(1)查询质数了

我们这里通过数筛法先建立质数表，后续建立表时直接查询即可。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,b) for (ll i=(a);i<(b);i++)
#define pb push_back

int n;
const int N = 60000;

// 传入 下标,原数组,本次dfs是否访问过vis, 可选路径，是否连接汇点，当前dfs上的点
bool dfs(int idx,const vector<int>&num,vector<bool>& vis, vector<vector<bool>> & path, vector<bool> & matched,vector<int> & ps){
  if(num[idx] % 2 && !matched[idx]){ // 找到出点
    matched[idx] = true; // 标记匹配
    // 反转ps中构成的边
    ps.pb(idx);
    rep(i,0,ll(ps.size())-1){
      path[ps[i]][ps[i+1]] = false;
      path[ps[i+1]][ps[i]] = true;
    }
    return true;
  }
  vis[idx] = true;
  ps.pb(idx); // 当前点加入
  rep(i,0,n){
    if(!path[idx][i])continue; // 有可选路径
    // 存在 idx -> i 的边
    if(vis[i])continue; // 未访问过
    bool r = dfs(i,num,vis,path,matched,ps);
    if(r)return r;
  }
  ps.pop_back(); // 当前点弹出
  return false;
}

int main(){
  // 大于1的质数表
  vector<bool> prime(N+10,true);
  rep(i,2,N){
    if(!prime[i])continue;
    rep(j,i,N){ // 筛数
      if(i*j>N)break;
      prime[i*j] = false;
    }
  }
  while(~scanf("%d",&n)){
    vector<int> num;
    int v;
    rep(i,0,n){
      scanf("%d",&v); // 读入
      num.pb(v);
    }
    // 已连接汇点
    vector<bool> matched(n,false);
    // 可选路径
    vector<vector<bool> > path(n,vector<bool>(n,false));
    rep(i,0,n){
      if(num[i]%2)continue;
      rep(j,0,n){
        if(num[j]%2 == 0)continue;
        if(!prime[num[i]+num[j]])continue; // 根据题意建立 从 偶 指向 奇 的满足和为质数的 可选路径
        path[i][j] = true;
      }
    }
    int ans = 0;
    rep(i,0,n){
      if(num[i]%2)continue; // 枚举所有偶数点
      vector<bool> vis(n,false);
      vector<int> ps = {};
      ans += dfs(i,num,vis,path,matched,ps);
    }
    printf("%d\n",ans);
  }
  return 0;
}

复杂度分析

时间复杂度: 前期初始化的复杂度，主要在建立边$O\left(n^2\right)O(n^2)$O(n2)和质数表初始化$O\left(max\right(a_i\left)\right)O(max(a\_i))$O(max(ai​)), 搜索过程中，每个偶数点触发一次dfs，一次dfs最坏情况，遍历所有边，所以搜索的过程中时间复杂度为$O\left(n^3\right)O(n^3)$O(n3), 总时间复杂度为$O\left(max\right(n^3,a_i\left)\right)O(max(n^3,a\_i))$O(max(n3,ai​))

空间复杂度: 空间分为三部分，

质数表$O\left(max\right(a_i\left)\right)O(max(a\_i))$O(max(ai​)),

建立的访问数组，路径数组，标识数组等，最大的是路径数组为$O\left(n^2\right)O(n^2)$O(n2)

递归栈消耗，因为中间全部是引用传递，其余是常量个变量，所以仅与栈深度相关为$O\left(n\right)O(n)$O(n)

所以空间复杂度为$O\left(max\right(a_i,n^2\left)\right)O(max(a\_i,n^2))$O(max(ai​,n2))