题意
有 \(i\) 种数，第 \(i\) 种数是 \(a_i\)，有 \(b_i\) 个。每次可以选择两个数 \(x,y\) 满足 \(x+y\) 为质数，将它们删除。问最多能删多少次。
思路
如果不存在 \(1\)，那么可以对 \(i \ne j\) 且 \(a_i + a_j\) 为质数的 \((i,j)\) 之间连边，容易证明这是一张二分图，因为 \(a_i\) 和 \(a_j\) 必然一奇一偶。那么做一遍二分图带权最大匹配，跑最大流即可。
现在问题就是 \(1\) 可以和自己删，我们需要在保证其他数字删的对数最多的前提下，保留的 \(1\) 的个数最多，使得最后删的最多。想到最小费用最大流，将 \(S \to i\) 且 \(a_i = 1\) 的弧的费用设为 \(1\)，其他弧的费用设为 \(0\)，最小费用就是最少删的 \(1\) 的个数。
代码
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 210;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
ll n, a[maxn], b[maxn], head[maxn], len, S = 208, T = 209;
struct edge {
ll to, next, cap, flow, cost;
} edges[maxn * maxn * 100];
void add_edge(ll u, ll v, ll c, ll f, ll co) {
edges[++len].to = v;
edges[len].next = head[u];
edges[len].cap = c;
edges[len].flow = f;
edges[len].cost = co;
head[u] = len;
}
struct MCMF {
ll dis[maxn], cur[maxn];
bool vis[maxn];
void add(ll u, ll v, ll c, ll co) {
add_edge(u, v, c, 0, co);
add_edge(v, u, 0, 0, -co);
}
bool spfa() {
mems(vis, 0);
mems(dis, 0x3f);
dis[S] = 0;
vis[S] = 1;
queue<int> q;
q.push(S);
while (q.size()) {
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = head[u]; i; i = edges[i].next) {
edge e = edges[i];
if (e.cap > e.flow && dis[e.to] > dis[u] + e.cost) {
dis[e.to] = dis[u] + e.cost;
if (!vis[e.to]) {
vis[e.to] = 1;
q.push(e.to);
}
}
}
}
return dis[T] < inf;
}
ll dfs(int u, ll a, ll &cost) {
if (u == T || !a) {
return a;
}
vis[u] = 1;
ll flow = 0, f;
for (ll &i = cur[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (!vis[e.to] && e.cap > e.flow && dis[e.to] == dis[u] + e.cost) {
if ((f = dfs(e.to, min(a, e.cap - e.flow), cost)) > 0) {
cost += f * e.cost;
e.flow += f;
edges[i ^ 1].flow -= f;
flow += f;
a -= f;
if (!a) {
break;
}
}
}
}
return flow;
}
void solve(ll &flow, ll &cost) {
flow = cost = 0;
while (spfa()) {
memcpy(cur, head, sizeof(head));
flow += dfs(S, inf, cost);
}
}
} solver;
bool check(ll x) {
for (ll i = 2; i * i <= x; ++i) {
if (x % i == 0) {
return 0;
}
}
return 1;
}
void solve() {
len = 1;
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld", &a[i], &b[i]);
}
for (int i = 1; i <= n; ++i) {
if (a[i] & 1) {
solver.add(S, i, b[i], a[i] == 1);
for (int j = 1; j <= n; ++j) {
if (a[j] % 2 == 0 && check(a[i] + a[j])) {
solver.add(i, j + n, inf, 0);
}
}
} else {
solver.add(i + n, T, b[i], 0);
}
}
ll flow, cost;
solver.solve(flow, cost);
ll ans = flow;
for (int i = 1; i <= n; ++i) {
if (a[i] == 1) {
ans += (b[i] - cost) / 2;
break;
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}