CF510E Fox And Dinner-蒲公英云

CF510E Fox And Dinner

题面

题解

首先可以发现：由于\(a_i \geq 2\)，所以质数肯定是被拆成一个奇数和一个偶数。

这样的话很类似一个二分图模型，所以考虑网络流。

当\(a_i\)是奇数时连边\((S, i, 2)\)，当\(a_i\)是偶数时连边\((i, T, 2)\)，表示一个点的邻居最多有两个点。

若\(a_i\)是奇数，\(a_j\)是偶数，\(a_i + a_j\)是质数，则连边\((i, j, 1)\)。

跑出来如果最大流不是\(n\)则不合法，否则直接暴力找环即可。

代码

#include <cstdio> #include <cstring> #include <algorithm> #include <queue> inline int read() { int data = 0, w = 1; char ch = getchar(); while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar(); if (ch == '-') w = -1, ch = getchar(); while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar(); return data * w; } const int N(205), LIM(20010), M(20000), INF(0x3f3f3f3f); struct edge { int next, to, cap; } e[N * N * 2]; int n, A[N], not_prime[LIM], head[N], e_num = -1, lev[N], cur[N], S, T; inline void Add(int from, int to, int cap) { e[++e_num] = (edge) {head[from], to, cap}, head[from] = e_num; e[++e_num] = (edge) {head[to], from, 0 }, head[to] = e_num; } void Init() { not_prime[1] = 1; for (int i = 2; i <= M; i++) if (!not_prime[i]) for (int j = i * i; j <= M; j += i) not_prime[j] = 1; } int bfs() { std::queue<int> Q; Q.push(S); memset(lev, 0, (T + 1) << 2), lev[S] = 1; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = head[x]; ~i; i = e[i].next) { int to = e[i].to; if (!e[i].cap || lev[to]) continue; lev[to] = lev[x] + 1, Q.push(to); } } return lev[T]; } int dfs(int x, int f) { if (x == T || !f) return f; int ans = 0, cap; for (int i = head[x]; ~i; i = e[i].next) { int to = e[i].to; if (e[i].cap && lev[to] == lev[x] + 1) { cap = dfs(e[i].to, std::min(f - ans, e[i].cap)); e[i].cap -= cap, e[i ^ 1].cap += cap, ans += cap; if (ans == f) break; } } if (!ans) lev[x] = 0; return ans; } int Dinic() { int ans = 0; while (bfs()) memcpy(cur, head, (T + 1) << 2), ans += dfs(S, INF); return ans; } std::vector<int> cir[N]; int tot, vis[N]; void find(int x) { if (1 <= x && x <= n) cir[tot].push_back(x); vis[x] = 1; for (int i = head[x]; ~i; i = e[i].next) if (!vis[e[i].to] && e[i | 1].cap == 1) find(e[i].to); } int main() { memset(head, -1, sizeof head); Init(), n = read(), S = 0, T = n + 1; int p = 0, q = 0; for (int i = 1; i <= n; i++) A[i] = read(), ((A[i] & 1) ? ++p : ++q); if (p != q) return puts("Impossible"), 0; for (int i = 1; i <= n; i++) if (A[i] & 1) for (int j = (Add(S, i, 2), 1); j <= n; j++) { if (!not_prime[A[i] + A[j]]) Add(i, j, 1); } else Add(i, T, 2); if (Dinic() != n) return puts("Impossible"), 0; for (int i = 1; i <= n; i++) if (!vis[i]) ++tot, find(i); printf("%d\n", tot); for (int i = 1; i <= tot; i++, puts("")) { printf("%lu ", cir[i].size()); for (int j : cir[i]) printf("%d ", j); } return 0; }