【解析】欧拉筛法，奇偶分析。建二分图，网络流



[Analysis]



http://blog.csdn.net/qq574857122/article/details/43453087。



所谓的连通块就是指满流了，因为我直接使用剩余流量求网络流。

至于怎样推断满流，我想到下面几种：

①对于初始的网络。若图的流向是一样的。那么就直接推断对于一条边k的正向边k>>1<<1是否满流。

②对于一般的，能够存流量限制。

③或者对每条边再存个tag。若tag=1，则表示初始时这条边容量限制非0，否则是0。



[Q&A]

问题1：为什么这样搜索能够出解而不错误？

回答1：这不是非常明显的嘛，因为满流了，所以除原点和汇点外的每一个节点连接且仅连接两个节点。

这样从一个节点过来。那么必定仅仅能从还有一个节点出去。

最后必定会有一个节点连接到第一个节点。这是就停止了。假如没有。那么一直找到了第n个节点就找不到了。矛盾。

特殊的，对于每一个连通集合的第一个节点，选择了随意一个相邻的节点，这也是没问题的。



[Sum]

①对于素数的问题，要想到奇偶分析。

②k!=-1。等价于~k，这里能够化简。事实上scanf("%d",&a)这个函数假设读不到不论什么东西，返回的值也是-1。

之所以能这样由于-1的二进制为最大即2^k-1，取反后为0。而其它取反都非0。

③推断满流的三种办法。

④回想了网络流算法。

[Code]

#include <cstdio>

#include <cstring>

#include <cstdlib>

using namespace std;

const int N=240;

const int M=N*N;

const int P=20001;

int n,odd[N],even[N];

int w[N],pri[P],vp[P];

struct G

{

	int v,f,nxt;

}map[M+M];

int tt,hd[N];

int level[N],q[N],h,t;

G list[N]; int tl,used[N],fs[N],num,cnt[N];

inline int read(void)

{

	int s=0; char c=getchar();

	for (;c<'0'||c>'9';c=getchar());

	for (;'0'<=c&&c<='9';c=getchar()) s=s*10+c-'0';

	return s;

}

inline void ins(int u,int v,int f)

{

	map[++tt].v=v;

	map[tt].f=f;

	map[tt].nxt=hd[u];

	hd[u]=tt;

}

int init(void)

{

	n=read();

	for (int i=1;i<=n;i++)

	{

		w[i]=read();

		if (w[i]&1)

			odd[++odd[0]]=i;

		else even[++even[0]]=i;

	}

	if (odd[0]^even[0]) return 0;

	for (int i=2;i<P;i++)

	{

		if (!vp[i]) pri[++pri[0]]=i;

		for (int j=1;j<=pri[0];j++)

		{

			if (i*pri[j]>=P) break;

			vp[i*pri[j]]=1;

			if (i%pri[j]==0) break;

		}

	}

	tt=-1; memset(hd,-1,sizeof hd);

	for (int i=1;i<=odd[0];i++)

	{

		ins(0,odd[i],2),ins(odd[i],0,0);

		for (int j=1;j<=even[0];j++)

			if (!vp[w[odd[i]]+w[even[j]]])

				ins(odd[i],even[j],1),ins(even[j],odd[i],0);

	}

	for (int i=1;i<=even[0];i++)

		ins(even[i],n+1,2),ins(n+1,even[i],0);

	return 1;

}

int BFS(void)

{

	memset(level,-1,sizeof level);

	h=0,t=1,q[t]=0,level[0]=0;

	int k;

	for (;h^t;)

	{

		k=q[++h];

		for (int r=hd[k];~r;r=map[r].nxt)

			if (map[r].f&&level[map[r].v]==-1)

			{

				level[map[r].v]=level[k]+1;

				if (map[r].v==n+1) return 1;

				q[++t]=map[r].v;

			}

	}

	return 0;

}

inline int min(int i,int j)

{

	return i<j?i:j;

}

int DFS(int now,int flow)

{

	if (now==n+1) return flow;

	int sum=0,tmp;

	for (int k=hd[now];~k;k=map[k].nxt)

		if (map[k].f&&level[now]+1==level[map[k].v])

		{

			tmp=DFS(map[k].v,min(flow,map[k].f));

			if (tmp)

			{

				map[k].f-=tmp;

				map[k^1].f+=tmp;

				flow-=tmp;

				sum+=tmp;

				if (!flow) break;

			}

			else level[map[k].v]=P;

		}

	return sum;

}

inline void inslist(int now)

{

	list[++tl].v=now;

	list[tl].nxt=fs[num];

	fs[num]=tl;

}

void dfs(int now,int fst)

{

	cnt[num]++;

	used[now]=1;

	inslist(now);

	for (int k=hd[now];k;k=map[k].nxt)

		if (!map[k>>1<<1].f&&map[k].v&&map[k].v^n+1)

		{

			if (fst==map[k].v) return;

			if (!used[map[k].v]) dfs(map[k].v,fst);

		}

}

int work(void)

{

	int sum=0;

	for (;BFS();) sum+=DFS(0,P);

	if (sum^n) return 0;

	for (int i=1;i<=n;i++)

		if (!used[i])

		{

			num++;

			dfs(i,i);

		}

	printf("%d\n",num);

	for (int i=1;i<=num;i++)

	{

		printf("%d ",cnt[i]);

		for (int j=fs[i];j;j=list[j].nxt)

			printf("%d ",list[j].v);

		printf("\n");

	}

	return 1;

}

int main(void)

{

	int d=init();

	if (d) d=work();

	if (!d) printf("Impossible\n");

	return 0;

}