题目链接 题意： 有 n 个数 ai，如果 ai + aj 是一个质数的 (i != j)，那么 (i, j) 是一个 pair。现在你可以选择最多 k 个 pair，问最多pair的并集最多有多少个数。n ≤ 3000, k ≤n*(n−1)/2, ai ≤1e6。 正解： 先不考虑 1 + 1 = 2 的情况，那么将奇数放在左边，偶数放在右边，跑二分图求出最大匹配，一开始两个两个消除。然后考虑把 1 加入的情况，那么 1 要不然自我消化，要不然和放在左边和一个偶数结合，那么把 1 一个一个加入并实时更新答案就好了, 最后一个一个消除就好了。时间复杂度 O(n^2)。
垃圾数据，上网搜题解，全是一般图上用魔改匈牙利跑最大匹配的，我tm服了，我还写了个魔改匈牙利去uoj上测一般图最大匹配，当然不可能全过，但竟然还过了15组？？学到了，这魔改匈牙利属实有点牛逼奥，早上1点起来开始搞，现在晚上7点，我真的爱死你了。
#include <bits/stdc++.h> #define mp make_pair #define fi first #define se second #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define forn(i, n) for (int i = 0; i < (int)(n); ++i) #define for1(i, n) for (int i = 1; i <= (int)(n); ++i) #define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i) #define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i) #define rep(i, l, r) for (int i = (l); i <= (r); i++) #define per(i, r, l) for (int i = (r); i >= (l); i--) #define ms(x, y) memset(x, y, sizeof(x)) using namespace std; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<pii> vpi; typedef vector<vi> vvi; typedef long long i64; typedef vector<i64> vi64; typedef vector<vi64> vvi64; typedef pair<i64, i64> pi64; typedef double ld; template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; } template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; } //1.integer overflow (1e5 * 1e5) (2e9 + 2e9) //2.runtime error //3.boundary condition const int N=3*(int)1e3+100; int tc,n,k,a[N],lx[N],ly[N],flag[2000100],prime[2000100],tot,vis[N],ok[N]; vvi G(N); void getPrime(){ tot=0; ms(flag,0); flag[0]=flag[1]=1; for(int i=2; i<=2000005; ++i){ if(!flag[i]) prime[++tot]=i; for(int j=1; j<=tot && i*prime[j]<=2000005; ++j){ flag[i*prime[j]]=1; if(i%prime[j]==0) break; } } } bool hungary(int x){ for(int to:G[x]){ if(!vis[to]){ vis[to]=1; if(ly[to]==0 || hungary(ly[to])){ lx[x]=to; ly[to]=x; return true; } } } return false; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout << fixed; #ifdef LOCAL_DEFINE freopen("input.txt", "r", stdin); #endif getPrime(); cin>>tc; while(tc--){ cin>>n>>k; vi odd,even; odd.clear(); even.clear(); for(int i=0; i<=n; ++i){ ok[i]=lx[i]=ly[i]=0; G[i].clear(); } int cnt=0; vector< int > one; for(int i=1; i<=n; ++i){ cin>>a[i]; if(a[i]==1){ ++cnt; one.eb(i); continue; } if(a[i]&1) odd.eb(i); else even.eb(i); } for(int i=0; i<int(odd.size()); ++i){ for(int j=0; j<int(even.size()); ++j){ if(!flag[a[odd[i]]+a[even[j]]]){ G[odd[i]].eb(even[j]); ok[odd[i]]=ok[even[j]]=1; } } } int now=0; for(int i=0; i<int(odd.size()); ++i){ if(lx[odd[i]]) continue; ms(vis,0); if(hungary(odd[i])) ++now; } for(;;){ if(!cnt) break; int pre=now; forn(i, int(even.size())){ if(!flag[a[even[i]]+1]){ G[one.back()].eb(even[i]); ok[one.back()]=ok[even[i]]=1; } } ms(vis,0); if(hungary(one.back())){ ++now; one.pop_back(); --cnt; } else{ break; } } if(cnt%2==0){ now=now+cnt/2; if(now>=k) cout<<2*k<<'\n'; else{ int temp=0; for(int i=1; i<=n; ++i){ if(a[i]==1) continue; if(!ok[i]) continue; if(a[i]%2==1){ if(!lx[i]) ++temp; } else{ if(!ly[i]) ++temp; } } temp=min(k-now,temp); now=now*2; now+=temp; cout<<now<<'\n'; } } else{ now=now+cnt/2; if(now>=k) cout<<2*k<<'\n'; else{ int temp=0; for(int i=1; i<=n; ++i){ if(a[i]==1) continue; if(!ok[i]) continue; if(a[i]%2==1){ if(!lx[i]) ++temp; } else{ if(!ly[i]) ++temp; } } for(int i=1; i<=n; ++i){ if(i==one.back()) continue; if(a[i]%2==1 && lx[i]) continue; if(a[i]%2==1 && ly[i]) continue; if(!flag[a[i]+1]){ ++temp; break; } } temp=min(k-now,temp); now=now*2; now+=temp; cout<<now<<'\n'; } } } #ifdef LOCAL_DEFINE cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif return 0; }