首页 > 代码库 > 网络流（最大流）CodeForces 512C：Fox And Dinner

网络流（最大流）CodeForces 512C：Fox And Dinner

2024-08-15 12:55:59   225人阅读

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:

  1. Each fox is sitting at some table.
  2. Each table has at least 3 foxes sitting around it.
  3. 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.

 

Input

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).

 

Output

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.

 

Sample Input

Input
4
3 4 8 9
Output
1
4 1 2 4 3
Input
5
2 2 2 2 2
Output
Impossible
Input
12
2 3 4 5 6 7 8 9 10 11 12 13
Output
1
12 1 2 3 6 5 12 9 8 7 10 11 4
Input
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
Output
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
　　建二分图，再用流量为2限制度数，即可用网络流AC。
  1 #include <iostream>  2 #include <cstring>  3 #include <cstdio>  4 #include <queue>  5 using namespace std;  6 const int N=210,M=60010,INF=1000000000;  7 int cnt,fir[N],fron[N],nxt[M],to[M],cap[M];  8 int dis[N],gap[N],path[N],vis[N],q[N],h,t;  9 int n,m,a[N],tp[N],tot;vector<int>ans[N]; 10 struct Net_Flow{ 11     void Init(){ 12         memset(fir,0,sizeof(fir)); 13         memset(gap,0,sizeof(gap)); 14         memset(dis,0,sizeof(dis)); 15         h=t=cnt=1; 16     } 17     void addedge(int a,int b,int c){ 18         nxt[++cnt]=fir[a];to[fir[a]=cnt]=b;cap[cnt]=c; 19         nxt[++cnt]=fir[b];to[fir[b]=cnt]=a;cap[cnt]=0; 20     } 21     bool BFS(int S,int T){ 22         dis[q[h]=T]=1; 23         while(h<=t){ 24             int x=q[h++]; 25             for(int i=fir[x];i;i=nxt[i]) 26                 if(!dis[to[i]])dis[q[++t]=to[i]]=dis[x]+1; 27         } 28         return dis[S]; 29     } 30     int ISAP(int S,int T){ 31         if(!BFS(S,T))return 0; 32         for(int i=S;i<=T;i++)gap[dis[i]]+=1; 33         for(int i=S;i<=T;i++)fron[i]=fir[i]; 34         int ret=0,f,p=S,Min; 35         while(dis[S]<=T+1){ 36             if(p==T){f=INF; 37                 while(p!=S){ 38                     f=min(f,cap[path[p]]); 39                     p=to[path[p]^1]; 40                 }ret+=f,p=T; 41                 while(p!=S){ 42                     cap[path[p]]-=f; 43                     cap[path[p]^1]+=f; 44                     p=to[path[p]^1]; 45                 } 46             } 47             for(int &i=fron[p];i;i=nxt[i]) 48                 if(cap[i]&&dis[to[i]]==dis[p]-1){ 49                     path[p=to[i]]=i;break; 50                 } 51             if(!fron[p]){ 52                 if(!--gap[dis[p]])break;Min=T+1; 53                 for(int i=fir[p];i;i=nxt[i]) 54                     if(cap[i])Min=min(Min,dis[to[i]]); 55                 gap[dis[p]=Min+1]+=1;fron[p]=fir[p]; 56                 if(p!=S)p=to[path[p]^1];     57             }     58         }     59         return ret; 60     } 61     void DFS(int x,int id){ 62         vis[x]=1;ans[id].push_back(x); 63         for(int i=fir[x];i;i=nxt[i]){ 64             if(vis[to[i]]||to[i]<1||to[i]>n)continue; 65             if(a[to[i]]%2==0&&cap[i^1]==0)DFS(to[i],id); 66             if(a[to[i]]%2!=0&&cap[i]==0)DFS(to[i],id); 67         } 68     } 69     void Solve(int S,int T){ 70         for(int x=1;x<=n;x++) 71             if(a[x]%2==0&&!vis[x]) 72                 DFS(x,++tot); 73         printf("%d\n",tot); 74         for(int i=1;i<=tot;i++){ 75             printf("%d ",ans[i].size()); 76             for(int j=0;j<ans[i].size();j++) 77                 printf("%d ",ans[i][j]); 78             puts("");     79         } 80     } 81 }isap; 82 int S,T; 83 bool Check(int x){ 84     for(int i=2;i*i<=x;i++) 85         if(x%i==0)return false; 86     return true;     87 } 88 int main(){ 89     scanf("%d",&n);isap.Init();T=n+1; 90     if(n%2==1){puts("Impossible");return 0;} 91     for(int i=1;i<=n;i++)scanf("%d",&a[i]); 92     for(int i=1;i<=n;i++){ 93         if(a[i]%2==0)isap.addedge(S,i,2); 94         else isap.addedge(i,T,2); 95     }     96     for(int i=1;i<=n;i++)if(a[i]%2==0) 97         for(int j=1;j<=n;j++)if(a[j]%2) 98             if(Check(a[i]+a[j])) 99                 isap.addedge(i,j,1);100     if(isap.ISAP(S,T)!=n){101         puts("Impossible");102         return 0;103     }            104     isap.Solve(S,T);105     return 0;106 }

 

网络流（最大流）CodeForces 512C：Fox And Dinner


联系
我们