题目描述
Fox Ciel is participating in a party in Prime Kingdom. There are $n$ foxes there (include Fox Ciel). The $i$-th fox is $a_i$ years old.
They will have dinner around some round tables. You want to distribute foxes such that:
- each fox is sitting at some table,
- each table has at least 3 foxes sitting around it,
- the sum of ages of any two adjacent foxes around each table should be a prime number.
If $k$ foxes $f_1, f_2, \ldots, f_k$ are sitting around table in clockwise order, then for $1 \le i \le k-1$: $f_i$ and $f_{i+1}$ are adjacent, and $f_1$ and $f_k$ are also adjacent.
If it is possible to distribute the foxes in the desired manner, find out a way to do that.
题意概述
给定$n$个数$a_i$,你需要将它们分成若干个圈,使得每个圈中至少有$3$个数,且任意两个相邻的数的和为质数。
数据范围:$3 \le n \le 200, \; 2 \le a_i \le 10000$。
算法分析
因为每个数都大于$1$,所以任意两个相邻的数必定是一奇一偶。对于任意一个奇数$a_i$和任意一个偶数$a_j$,如果$a_i+a_j$是质数,那么就由$a_i$向$a_j$连一条流量为$1$的边。由于每个数都必须与另外两个数相连,因此可以由一个假设的源点向每个奇数的点连一条流量为$2$的边,由每个偶数的点向一个假设的汇点连一条流量为$2$的边。找出这张图的最大流,如果源点连出的边和连向汇点的边全部满流则说明有解。最后遍历找出所有环即可。
代码
#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; }