网络流。
原点到偶数连边，容量为2，
奇数到汇点连边，容量为2，
偶数到与之能凑成素数的奇数连边，容量为1
如果奇数个数不等于偶数个数，输出不可能
如果原点到偶数的边不满流，输出不可能
剩下的情况有解：因为一个偶数点选了两个奇数点，一个奇数点被两个偶数点选择，一定能构造出环。
#include<cstdio> #include<cstring> #include<string> #include<cmath> #include<vector> #include<queue> #include<algorithm> using namespace std; const int maxn = 500 + 10; const int INF = 0x7FFFFFFF; struct Edge { int from, to, cap, flow; Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f){} }; vector<Edge>edges; vector<int>G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; int n, m, s, t; int num[maxn]; vector<int>g[maxn]; vector<int> ans[maxn]; bool f[maxn]; int block; void init() { for (int i = 0; i < maxn; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); int w = edges.size(); G[from].push_back(w - 2); G[to].push_back(w - 1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue<int>Q; Q.push(s); d[s] = 0; vis[s] = 1; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i<G[x].size(); i++) { Edge e = edges[G[x][i]]; if (!vis[e.to] && e.cap>e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a) { if (x == t || a == 0) return a; int flow = 0, f; for (int &i = cur[x]; i<G[x].size(); i++) { Edge e = edges[G[x][i]]; if (d[x]+1 == d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0) { edges[G[x][i]].flow+=f; edges[G[x][i] ^ 1].flow-=f; flow+=f; a-=f; if(a==0) break; } } if(!flow) d[x] = -1; return flow; } int dinic(int s, int t) { int flow = 0; while (BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow; } bool prime(int x) { for(int i=2;i*i<=x;i++) if(x%i==0) return 0; return 1; } void Find(int now) { f[now]=1; ans[block].push_back(now); for(int i=0;i<g[now].size();i++) { if(f[g[now][i]]) continue; Find(g[now][i]); } } int main() { while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) scanf("%d",&num[i]); init(); s=0;t=n+1; int e1=0,e2=0; int flag=0; for(int i=1;i<=n;i++) { if(num[i]%2==0) { e1++; AddEdge(s,i,2); } else { e2++; AddEdge(i,t,2); } } if(e1!=e2) flag=1; else { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(num[i]%2==0&&num[j]%2==1&&prime(num[i]+num[j])) AddEdge(i,j,1); int Flow=dinic(s,t); if(Flow!=2*e1) flag=1; } if(flag==1) printf("Impossible "); else { block=0; memset(f,0,sizeof f); for(int i=0;i<maxn;i++) { g[i].clear(); ans[i].clear(); } for(int i=0;i<edges.size();i=i+2) { if(edges[i].flow==1) { int u=edges[i].from; int v=edges[i].to; g[u].push_back(v); g[v].push_back(u); } } for(int i=1;i<=n;i++) { if(f[i]) continue; Find(i); block++; } printf("%d ",block); for(int i=0;i<block;i++) { printf("%d ",ans[i].size()); for(int j=0;j<ans[i].size();j++) printf("%d ",ans[i][j]); printf(" "); } } } return 0; }