Prime Set(二分图匹配)

描述

传送门:2017中国大学生程序设计竞赛-秦皇岛站

Given an array of $n$ integers $a_1, a_2, \dots, a_n$, we say a set $\lbrace i, j\rbrace$ is a prime set of the given array, if $i \ne j$ and $a_i + a_j$ is prime.

BaoBao has just found an array of $n$ integers $a_1, a_2, \dots, a_n$ in his pocket. He would like to select at most $k$ prime set of that array to maximize the size of the union of the selected sets. That is to say, to maximize $|\bigcup\limits_{i = 1}^{m}p_i|$ by carefully selecting $m$ and $p_1, p_2, \dots, p_m$, where $m \le k$ and $p_i$ is a prime set of the given array. Please help BaoBao calculate the maximum size of the union set.

Input

There are multiple test cases. The first line of the input is an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $k$ ($1 \le n \le 3\times 10^3$, $0 \le k \le \frac{n(n-1)}{2}$), their meanings are described above.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$), indicating the given array.

It’s guaranteed that the sum of $n$ over all test cases will not exceed $10 ^ 4$.

Output

For each test case output one line containing one integer, indicating the maximum size of the union of at most $k$ prime set of the given array.

Sample Input

1
2
3
4
5
6
7
8
9
4
4 2
2 3 4 5
5 3
3 4 12 3 6
6 3
1 3 6 8 1 1
1 0
1

Sample Output

1
2
3
4
4
3
6
0

Hint

For the first sample test case, there are 3 prime sets: {1, 2}, {1, 4} and {2, 3}. As $k = 2$, we can select {1, 4} and {2, 3} to get the largest union set {1, 2, 3, 4} with a size of 4.

For the second sample test case, there are only 2 prime sets: {1, 2} and {2, 4}. As $k = 3$, we can select both of them to get the largest union set {1, 2, 4} with a size of 3.

For the third sample test case, there are 7 prime sets: {1, 3}, {1, 5}, {1, 6}, {2, 4}, {3, 5}, {3, 6} and {5, 6}. As $k = 3$, we can select {1, 3}, {2, 4} and {5, 6} to get the largest union set {1, 2, 3, 4, 5, 6} with a size of 6.

思路

  • 考虑所有的质数除了$2$之外都是奇数,所以除去$1,1$的匹配之外,都是一奇一偶的匹配。显然是个二分图匹配。所以可以先建图跑一遍二分图匹配,得到最大匹配。每个匹配对答案的贡献为$2$。
  • 然后再看有没有$1,1$的匹配,这也是对答案贡献为$2$。然后考虑对答案贡献为$1$的部分,即一个已经被匹配了,而另一个没有被匹配的情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

const int maxn = 3005;

const int N = 2e6 + 5;
bool notprime[N] = {1, 1};
void GetPrime()
{
for (int i = 2; i < N; i++)
if (!notprime[i] && i <= N / i)
for (int j = i * i; j < N; j += i)
notprime[j] = 1;
}

int a[maxn];

struct Match
{
int n;
vector<int> G[maxn];
int linker[maxn];
bool vis[maxn];
inline void init(int n)
{
this->n = n;
for (int i = 0; i < n; i++) G[i].clear();
}
inline void addedge(int u, int v) { G[u].pb(v); }
bool dfs(int u)
{
for (auto v : G[u])
{
if (!vis[v])
{
vis[v] = true;
if (linker[v] == -1 || dfs(linker[v]))
{
linker[v] = u;
return true;
}
}
}
return false;
}
int MaxMatch()
{
int ans = 0;
clr(linker, -1);
for (int u = 0; u < n; u++)
{
clr(vis, 0);
if (dfs(u)) ans++;
}
return ans;
}
bool mark[maxn];
int solve(int n, int k)
{
clr(mark, 0);
int match = MaxMatch();
int ans = min(k, match);
match = ans;
for (int i = 0; i < n; i++)
if (linker[i] != -1)
mark[i] = mark[linker[i]] = 1;
ans <<= 1;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (match < k && a[i] == 1 && a[j] == 1 && mark[i] == 0 && mark[j] == 0)
match++, ans += 2, mark[i] = mark[j] = 1;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (match < k && !notprime[a[i] + a[j]] && (mark[i] ^ mark[j]))
match++, ans++, mark[i] = mark[j] = 1;
return ans;
}
} gao;

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
GetPrime();
int T;
scanf("%d", &T);
while (T--)
{
int n, k;
scanf("%d%d", &n, &k);
gao.init(n);
for (int i = 0; i < n; i++) scanf("%d", a + i);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (!notprime[a[i] + a[j]] && (a[i] != 1 || a[j] != 1))
{
if (a[i] & 1)
gao.addedge(i, j);
else
gao.addedge(j, i);
}
printf("%d\n", gao.solve(n, k));
}
return 0;
}
捐助作者