题目链接:素数伴侣_牛客题霸_牛客网
解法:最大匹配
因为素数不可能是偶数,所以“素数伴侣”只能是一个奇数和一个偶数。由此我们可以创建二分图:一个子集全是奇数,另一个子集全是偶数,若两个节点值之和为素数则连接一条边。二分图创建好后就是求最大匹配问题了,可以用匈牙利算法或者最大流算法求解(判断素数可以用线性筛)
代码示例1(匈牙利算法):
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <type_traits>
#include <vector>
using namespace std;
const int V = 60010, N = 105, M = 5010;
vector<int> primes;
bool tag[V];
int h[N], to[M], ne[M], idx;
void Add(int u, int v) {
to[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
void Init() {
fill_n(h, N, -1);
primes.reserve(3000);
for (int i = 2; i < V; i++) {
if (!tag[i]) primes.push_back(i);
for (auto j : primes) {
if (i * j >= V) break;
tag[i * j] = true;
if (i % j == 0) break;
}
}
}
int ar[N];
int match[N];
bool flag[N];
int n;
bool DFS(int u) {
flag[u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int v = to[i];
if (flag[v]) continue;
flag[v] = true;
if (!match[v] || DFS(match[v])) {
match[v] = u;
return true;
}
}
return false;
}
int main() {
Init();
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", ar + i);
for (int j = i - 1; j > 0; j--) {
if (!tag[ar[i] + ar[j]]) {
Add(i, j);
Add(j, i);
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (ar[i] % 2) {
fill_n(flag, N, false);
if (DFS(i)) ++ans;
}
}
printf("%d", ans);
}
代码示例2(最大流ISAP)
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <type_traits>
#include <vector>
#include <queue>
using namespace std;
const int V = 60010, N = 105, M = 5010;
vector<int> primes;
bool tag[V];
int h[N], to[M], ne[M], wt[M], idx;
void Add(int u, int v, int w) {
to[idx] = v, wt[idx] = w, ne[idx] = h[u], h[u] = idx++;
}
void Init() {
fill_n(h, N, -1);
primes.reserve(3000);
for (int i = 2; i < V; i++) {
if (!tag[i]) primes.push_back(i);
for (auto j : primes) {
if (i * j >= V) break;
tag[i * j] = true;
if (i % j == 0) break;
}
}
}
int ar[N];
int n;
// 源点、汇点
int ss, tt;
// 各个结点所在层
int layer[N];
// 各层节点数量
int cnt[N];
void BFS() {
queue<int> qu;
qu.push(tt);
layer[tt] = 1;
cnt[1] = 1;
int u, v;
while (qu.size()) {
u = qu.front();
qu.pop();
for (int i = h[u]; ~i; i = ne[i]) {
v = to[i];
if (layer[v]) continue;
layer[v] = layer[u] + 1;
++cnt[layer[v]];
qu.push(v);
}
}
}
int DFS(int u, int from, int inflow) {
if (u == tt) return inflow;
int res = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = to[i], & w = wt[i];
if (layer[v] != layer[u] - 1 || !w) continue;
int outflow = DFS(v, i, min(inflow, w));
w -= outflow;
if (~from) wt[from] += outflow;
res += outflow;
inflow -= outflow;
if (!inflow) return res;
}
if (!--cnt[layer[u]++]) layer[ss] = n << 1;
++cnt[layer[u]];
return res;
}
int main() {
Init();
scanf("%d", &n);
ss = n + 1, tt = n + 2;
for (int i = 1; i <= n; i++) {
scanf("%d", ar + i);
if (ar[i] % 2) {
Add(ss, i, 1);
Add(i, ss, 0);
}
else {
Add(i, tt, 1);
Add(tt, i, 0);
}
for (int j = i - 1; j > 0; j--) {
if (!tag[ar[i] + ar[j]]) {
Add(i, j, 1);
Add(j, i, 1);
}
}
}
int ans = 0;
BFS();
while (layer[ss] <= n + 2) ans += DFS(ss, -1, 1 << 30);
printf("%d", ans);
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)