[ABC263G] Erasing Prime Pairs

题目

思路

看到配对，想到网络流。

考虑如果一个点是奇数，那么将源点与其连接，如果是偶数，那么将汇点与其连接，如果一对奇数和偶数的和是质数，那么将它们两对应的点相连。其中，我们要对 1 特殊处理，因为 \(1 + 1 = 2\) 而 \(2\) 是偶数且是质数，所以考虑费用流，尽可能多地保留 \(1\)，对所有不是 \(1\) 的奇数，连边不要费用，对于 \(1\)，费用为 \(1\)。最后答案为 \(maxflow + \left\lfloor\dfrac{mincost}{2}\right\rfloor\)。

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 5010, M = 100010, INF = 0x3f3f3f3f3f3f3f3f;

struct edge {
    int to, next, w, cost; 
} e[M];

int head[N], idx = 1;

void add(int u, int v, int w, int cost) {
    idx++;
    e[idx].to = v;
    e[idx].next = head[u];
    e[idx].w = w;
    e[idx].cost = cost;
    head[u] = idx;
    
    idx++;
    e[idx].to = u;
    e[idx].next = head[v];
    e[idx].w = 0;
    e[idx].cost = -cost;
    head[v] = idx;
}

int n, S, T;
int dis[N], pre[N], flow[N];
bool st[N];

bool spfa() {
    queue<int> q;
    q.push(S);
    memset(dis, 0x3f, sizeof(dis));
    memset(flow, 0, sizeof(flow));
    dis[S] = 0;
    flow[S] = INF;
    st[S] = true;
    
    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;
        
        for (int i = head[t]; i; i = e[i].next) {
            int to = e[i].to;
            if (e[i].w && dis[to] > dis[t] + e[i].cost) {
                dis[to] = dis[t] + e[i].cost;
                pre[to] = i;
                flow[to] = min(flow[t], e[i].w);
                if (!st[to]) {
                    q.push(to);
                    st[to] = true;
                }
            }
        }
    }
    return flow[T] > 0;
}

int a[N], b[N];

bool prime(int x) {
    if (x <= 2) return false;
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    S = n + 1, T = n + 2;
    int cnt1 = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] % 2 == 1) {
            add(S, i, b[i], a[i] == 1);
            if (a[i] == 1) cnt1 += b[i];
        }
        else {
            add(i, T, b[i], 0);
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (prime(a[i] + a[j]) && a[i] % 2 == 1 && a[j] % 2 == 0) {
                add(i, j, 0x3f3f3f3f3f3f3f3f, 0);
            }
        }
    }
    
    int maxflow = 0, mincost = 0;
    while (spfa()) {
        maxflow += flow[T];
        mincost += flow[T] * dis[T];
        
        int x = T;
        while (x != S) {
            e[pre[x]].w -= flow[T];
            e[pre[x] ^ 1].w += flow[T];
            x = e[pre[x] ^ 1].to;
        }
    }
    cout << maxflow + (cnt1 - mincost) / 2 << '\n';
    return 0;
}