2 seconds
256 megabytes
standard input
standard output
Fox Ciel is participating in a party in Prime Kingdom. There are n foxes there (include Fox Ciel). The i-th fox is ai 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 f1, f2, ..., fk are sitting around table in clockwise order, then for 1 ≤ i ≤ k - 1: fi and fi + 1 are adjacent, and f1 and fk are also adjacent.
If it is possible to distribute the foxes in the desired manner, find out a way to do that.
The first line contains single integer n (3 ≤ n ≤ 200): the number of foxes in this party.
The second line contains n integers ai (2 ≤ ai ≤ 104).
If it is impossible to do this, output "Impossible".
Otherwise, in the first line output an integer m (): the number of tables.
Then output m lines, each line should start with an integer k -=– the number of foxes around that table, and then k numbers — indices of fox sitting around that table in clockwise order.
If there are several possible arrangements, output any of them.
4
3 4 8 9
1
4 1 2 4 3
5
2 2 2 2 2
Impossible
12
2 3 4 5 6 7 8 9 10 11 12 13
1
12 1 2 3 6 5 12 9 8 7 10 11 4
24
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3
6 1 2 3 6 5 4
10 7 8 9 12 15 14 13 16 11 10
8 17 18 23 22 19 20 21 24
In example 1, they can sit around one table, their ages are: 3-8-9-4, adjacent sums are: 11, 17, 13 and 7, all those integers are primes.
In example 2, it is not possible: the sum of 2+2 = 4 is not a prime number.
题意：给你n只狐狸，每只狐狸的年龄，你可以任意选择狐狸组成一张桌子，使得满足条件，并且全部坐上桌子；
条件：1、一张桌子最少最三只狐狸。二、相邻的两只狐狸年龄相加为素数，最后一只与第一只相邻。3都要坐上桌子。
思路：因为两两相加为素数，两个奇数不可能相加为素数（题目中每个数都大于2），所以相邻为一奇一偶，并且奇数个数等于偶数个数；
这样就可以把奇数与偶数分开，建立二分图，每个点需要匹配两个点，使得条件满足；
源点与奇数建流，并且流量为2，同理，偶数与汇点建流；最大流等于n满足答案的条件。
最后dfs暴力找答案的环；
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define PI acos(-1.0)
const int maxn=1e5+,maxm=1e5+,inf=0x3f3f3f3f,mod=1e9+,N=1e5+;
const ll INF=1e18+; vector<vector<int> >Ans;
vector<int>out;
int flag[N];
struct Dinic
{
struct edge
{
int from,to,cap,flow;
};
vector<edge>es;
vector<int>G[maxn];
bool vis[maxn];
int dist[maxn];
int iter[maxn];
void init(int n)
{
for(int i=; i<=n+; i++) G[i].clear();
es.clear();
}
void addedge(int from,int to,int cap)
{
es.push_back((edge)
{
from,to,cap,
});
es.push_back((edge)
{
to,from,,
});
int x=es.size();
G[from].push_back(x-);
G[to].push_back(x-);
}
bool BFS(int s,int t)
{
memset(vis,,sizeof(vis));
queue <int> Q;
vis[s]=;
dist[s]=;
Q.push(s);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
for (int i=; i<G[u].size(); i++)
{
edge &e=es[G[u][i]];
if (!vis[e.to]&&e.cap>e.flow)
{
vis[e.to]=;
dist[e.to]=dist[u]+;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int u,int t,int f)
{
if(u==t||f==) return f;
int flow=,d;
for(int &i=iter[u]; i<G[u].size(); i++)
{
edge &e=es[G[u][i]];
if(dist[u]+==dist[e.to]&&(d=DFS(e.to,t,min(f,e.cap-e.flow)))>)
{
e.flow+=d;
es[G[u][i]^].flow-=d;
flow+=d;
f-=d;
if (f==) break;
}
}
return flow;
}
int Maxflow(int s,int t)
{
int flow=;
while(BFS(s,t))
{
memset(iter,,sizeof(iter));
int d=;
while(d=DFS(s,t,inf)) flow+=d;
}
return flow;
}
void solve(int u)
{
out.push_back(u);
for(int i=;i<G[u].size();i++)
{
edge x=es[G[u][i]];
//cout<<u<<" "<<x.from<<" "<<x.to<<" "<<x.flow<<endl;
if(flag[x.to]||x.flow==)continue;
flag[x.to]=;
solve(x.to);
}
}
} Din;
int a[N];
int vis[N];
void prime()
{
for(int i=; i<=; i++)
{
if(vis[i])continue;
for(int j=i+i; j<=; j+=i)
vis[j]=;
}
}
int main()
{
prime();
int n;
scanf("%d",&n);
Din.init(n);
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
if(a[i]%)Din.addedge(,i,);
else Din.addedge(i,n+,);
}
for(int i=; i<=n; i++)
{
for(int j=i+; j<=n; j++)
{
if(a[i]%&&a[j]%==)
{
if(!vis[a[i]+a[j]])
Din.addedge(i,j,);
}
else if(a[i]%==&&a[j]%)
{
if(!vis[a[i]+a[j]])
Din.addedge(j,i,);
}
}
}
int ans=Din.Maxflow(,n+); if(ans==n){
flag[]=;
flag[n+]=;
for(int i=;i<=n;i++)
{
if(!flag[i])
{
out.clear();
flag[i]=;
Din.solve(i);
Ans.push_back(out);
}
}
printf("%d\n",Ans.size());
for(int i=;i<Ans.size();i++)
{
printf("%d",Ans[i].size());
for(int j=;j<Ans[i].size();j++)
printf(" %d",Ans[i][j]);
printf("\n");
}
}
else
printf("Impossible\n");
return ;
}