题目链接

题面：

题意：

给出n个人， 以及每个人的值ai， 要求他们坐在一些桌子上面， 每个桌子如果有人坐， 就必须做3个人以上。　并且相邻的两个人的值加起来必须是素数。每个人的值都>=2.

题解：
由大于等于2这个条件， 可以知道出现的素数都是奇数（若相邻两个人的值的和为素数，那么一定是奇数）， 那么很明显就需要一奇一偶相邻这样做， 那么一个桌子上必定有偶数个人。 一个奇数旁边有两个偶数， 一个偶数旁边有两个奇数。

①、那么我们建立一个源点，将源点连入各个奇数节点，设定权值为2，表示其可以有两个相邻的小伙伴。

②、那么我们再建立一个汇点，将各个偶数节点连入汇点，设定权值为2，表示其可以有两个相邻的小伙伴。

③、那么如果左边某个奇数加上右边某个偶数能够构成一个素数，那么其建一条有向边，从奇数连入偶数，设定权值为1.

这样跑一遍网络流， 看结果是否等于n（是否满流）， 如果不相等， 说明不可能。如果相等， dfs一下就可以求出几个桌子， 每个桌子上面几个人了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<set>
#define ll long long
#define pr make_pair
#define pb push_back
#define ui unsigned int
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define forhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1000000007;
const double eps=1e-8;
const double pi=acos(-1.0);
const int maxn=210;
const int maxm=50100;
const int up=100000;

int head[maxn],ver[maxm],edge[maxm],nt[maxm],tot=1;
int d[maxn],a[maxn];
int n,s,t;
bool hh[maxn];
queue<int>q;
vector<int>vc[maxn];


void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z,nt[tot]=head[x],head[x]=tot;
    ver[++tot]=x,edge[tot]=0,nt[tot]=head[y],head[y]=tot;
}

bool bfs(void)
{
    memset(d,0,sizeof(d));
    while(q.size()) q.pop();

    q.push(s);
    d[s]=1;

    while(q.size())
    {
        int x=q.front();
        q.pop();

        forhead(x)
        {
            int y=ver[i];
            if(edge[i]&&!d[y])
            {
                q.push(y);
                d[y]=d[x]+1;
                if(y==t) return true;
            }
        }
    }
    return false;
}

int dinic(int x,int flow)
{
    if(x==t) return flow;
    int rest=flow ,k;

    for(int i=head[x];i&&rest;i=nt[i])
    {
        int y=ver[i];
        if(edge[i]&&d[y]==d[x]+1)
        {
            k=dinic(y,min(rest,edge[i]));
            if(!k) d[y]=0;

            edge[i]-=k;
            edge[i^1]+=k;
            rest-=k;
        }
    }
    return flow-rest;
}

int getmaxx(void)
{
    int flow=0,maxflow=0;
    while(bfs())
        while(flow=dinic(s,inf))
            maxflow+=flow;
    return maxflow;
}

int prime[maxm],cnt=0;
bool ha[maxm];

void Prime(void)
{
    ha[1]=true;
    for(int i=2;i<maxm;i++)
    {
        if(!ha[i]) prime[cnt++]=i;
        for(int j=0;j<cnt&&prime[j]*i<maxm;j++)
        {
            ha[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

void dfs(int x,int cnt)
{
    vc[cnt].pb(x);
    hh[x]=true;
    forhead(x)
    {
        int y=ver[i];
        if(hh[y]) continue;
        if(y==s||y==t) continue;
        if((i&1)==0&&edge[i]==0)
            dfs(y,cnt);
        else if((i&1)!=0&&edge[i]!=0)
            dfs(y,cnt);
    }
}

int main(void)
{
    Prime();
    int n;
    scanf("%d",&n);
    s=n+1,t=s+1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]&1) add(s,i,2);
        else add(i,t,2);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if((a[i]&1)&&!(a[j]&1))
            {
                if(!ha[a[i]+a[j]])
                    add(i,j,1);
            }
        }
    }
    int ans=getmaxx();
    if(ans!=n)
    {
        printf("Impossible\n");
        return 0;
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        if(!hh[i])
            dfs(i,++res);
    }
    cout<<res<<endl;
    for(int i=1;i<=res;i++)
    {
        printf("%d ",vc[i].size());
        for(auto x:vc[i])
            printf("%d ",x);
        putchar('\n');
    }

    return 0;
}