\(\mathcal{Description}\)
Link.
给定正整数集合 \(\{a_n\}\)，求一种把这些数放置在任意多个圆环上的方案，使得每个环的大小大于 \(2\) 且环上相邻两数之和是素数。
\(n\le200\)，\(2\le a_i\le10^4\)。
\(\mathcal{Solution}\)
这题怎么也黑了呢 qwq……
考虑到 \(2\le a_i\)，有 \(4\le a_i+a_j\)，所以素数必然是奇素数，而一个环必然是偶环。一个常见的套路是奇偶分开建对偶图，不妨设左侧奇数右侧偶数，源点 \(S\) 向所有奇数连边，容量为 \(2\)（环上与两个数相邻）；奇数向与之加和为素数的偶数连边，容量为 \(1\)（环大小大于 \(2\)）；偶数向汇点 \(T\) 连边，容量为 \(2\)。跑最大流再根据残余网络输出方案即可。
\(\mathcal{Code}\)
#include <queue>
#include <cstdio>
#include <vector>
const int MAXN = 200, MAXV = 2e4, INF = 0x3f3f3f3f;
int n, pn, oc, ec, S, T, ecnt = 1, a[MAXN + 5], pr[MAXV + 5];
int d[MAXN + 5], head[MAXN + 5], curh[MAXN + 5], ref[MAXN + 5];
bool vis[MAXV + 5], mtc[MAXN + 5];
std::vector<int> odd, even;
std::vector<std::vector<int> > table;
struct Edge { int to, flow, nxt; } graph[MAXN * 2 + MAXN * MAXN / 2 + 5];
inline void link ( const int s, const int t, const int f ) {
graph[++ ecnt] = { t, f, head[s] };
head[s] = ecnt;
}
inline void addEdge ( const int s, const int t, const int f ) {
link ( s, t, f ), link ( t, s, 0 );
}
inline void sieve ( const int n ) {
vis[1] = true;
for ( int i = 2; i <= n; ++ i ) {
if ( ! vis[i] ) pr[++ pn] = i;
for ( int j = 1; j <= pn && i * pr[j] <= n; ++ j ) {
vis[i * pr[j]] = true;
if ( ! ( i % pr[j] ) ) break;
}
}
}
inline int DFS ( const int u, int iflow ) {
if ( u == T ) return iflow;
int oflow = 0;
for ( int& i = curh[u], v, of; i; i = graph[i].nxt ) {
if ( d[v = graph[i].to] == d[u] + 1 && graph[i].flow ) {
of = DFS ( v, std::min ( iflow, graph[i].flow ) );
oflow += of, graph[i].flow -= of, graph[i ^ 1].flow += of;
if ( ! ( iflow -= of ) ) break;
}
}
if ( ! oflow ) d[u] = -1;
return oflow;
}
inline bool BFS () {
static std::queue<int> que;
for ( int i = 1; i <= T; ++ i ) d[i] = -1;
que.push ( S ), d[S] = 0;
for ( int u; ! que.empty (); que.pop () ) {
u = que.front ();
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ! ~ d[v = graph[i].to] && graph[i].flow ) {
que.push ( v ), d[v] = d[u] + 1;
}
}
}
return ~ d[T];
}
inline int Dinic () {
int ret = 0;
for ( ; BFS (); ret += DFS ( S, INF ) ) {
for ( int i = 1; i <= T; ++ i ) {
curh[i] = head[i];
}
}
return ret;
}
inline void match ( const int u, std::vector<int>& now ) {
now.push_back ( u ), mtc[u] = true;
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( ! mtc[v = graph[i].to] && v < S
&& ( ( u <= oc && graph[i ^ 1].flow ) || ( u > oc && graph[i].flow ) ) ) {
match ( v, now );
break;
}
}
}
int main () {
scanf ( "%d", &n );
int mx = 0;
for ( int i = 1; i <= n; ++ i ) {
scanf ( "%d", &a[i] );
if ( mx < a[i] ) mx = a[i];
if ( a[i] & 1 ) odd.push_back ( a[i] );
else even.push_back ( a[i] );
}
sieve ( mx << 1 );
oc = odd.size (), ec = even.size ();
S = oc + ec + 1, T = S + 1;
for ( int i = 1, ot = 0, ct = 0; i <= n; ++ i ) {
if ( a[i] & 1 ) ref[++ ot] = i;
else ref[oc + ++ ct] = i;
}
for ( int i = 1; i <= oc; ++ i ) addEdge ( S, i, 2 );
for ( int i = 1; i <= ec; ++ i ) addEdge ( i + oc, T, 2 );
for ( int i = 0; i ^ oc; ++ i ) {
for ( int j = 0; j ^ ec; ++ j ) {
if ( ! vis[odd[i] + even[j]] ) {
addEdge ( i + 1, oc + j + 1, 1 );
}
}
}
int f = Dinic ();
if ( f < n ) return puts ( "Impossible" ), 0;
std::vector<int> now;
for ( int i = 1; i <= oc; ++ i ) {
if ( ! mtc[i] ) {
now.clear ();
match ( i, now );
table.push_back ( now );
}
}
printf ( "%d\n", ( int ) table.size () );
for ( auto ele: table ) {
printf ( "%d", ( int ) ele.size () );
for ( int v: ele ) printf ( " %d", ref[v] );
putchar ( '\n' );
}
return 0;
}