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
| #include <iostream> #include <cstring> #include <cmath> #include <vector> using namespace std; struct edge { int v, f, nxt; } e[50001]; int n, nume = 1, top, src, sink, a[202], h[202], g[202], dist[202], que[202]; bool vis[202]; vector<int> ans[201]; void add_edge(int u, int v, int f) { e[++nume].v = v, e[nume].f = f, e[nume].nxt = h[u], h[u] = nume; e[++nume].v = u, e[nume].f = 0, e[nume].nxt = h[v], h[v] = nume; } void bfs() { memset(dist, 0, sizeof(dist)); que[1] = src, dist[src] = 1; int s = 0, t = 1; while (s < t) { int u = que[++s]; for (int i = h[u]; i; i = e[i].nxt) { if (e[i].f && !dist[e[i].v]) { que[++t] = e[i].v, dist[e[i].v] = dist[u] + 1; } } } } int dfs(int u, int delta) { if (u == sink) return delta; int ret = 0; for (int i = g[u]; i; i = e[i].nxt) { if (e[i].f && dist[e[i].v] == dist[u] + 1) { int dd = dfs(e[i].v, min(e[i].f, delta)); e[i].f -= dd, e[i ^ 1].f += dd; if (e[i].f) g[u] = i; delta -= dd, ret += dd; } } return ret; } int max_flow() { int ret = 0; while (1) { bfs(); if (!dist[sink]) return ret; for (int i = 0; i <= n + 1; ++i) g[i] = h[i]; ret += dfs(src, 1e9); } } bool is_prime(int t) { int k = (int) sqrt(t); for (int i = 2; i <= k; ++i) if (!(t % i)) return false; return true; } void find(int u, int t) { vis[u] = true, ans[t].push_back(u); for (int i = h[u]; i; i = e[i].nxt) { if (e[i].v && e[i].v != n + 1 && e[i].f == !(a[u] & 1) && !vis[e[i].v]) find(e[i].v, t); } } int main() { cin >> n; src = 0, sink = n + 1; for (int i = 1; i <= n; ++i) { cin >> a[i]; if (a[i] & 1) add_edge(src, i, 2); else add_edge(i, sink, 2); } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (a[i] & 1 && !(a[j] & 1) && is_prime(a[i] + a[j])) add_edge(i, j, 1); } } max_flow(); for (int i = h[0]; i; i = e[i].nxt) { if (e[i].f) { cout << "Impossible" << endl; return 0; } } for (int i = h[n + 1]; i; i = e[i].nxt) { if (e[i].f < 2) { cout << "Impossible" << endl; return 0; } } for (int i = 1; i <= n; ++i) if (!vis[i]) top++, find(i, top); cout << top << endl; for (int i = 1; i <= top; ++i) { cout << ans[i].size() << ' '; for (vector<int>::iterator iter = ans[i].begin(); iter != ans[i].end(); ++iter) { cout << *iter << ' '; } cout << endl; } return 0; }
|