题意简述
给定个数，，把这个数分成几组，使得每组中能排出一个序列，并且相邻两个和都是质数。输出方案。
思路
注意：。所以，我们将按奇偶分类，只有奇数能和偶数在一块，奇数和奇数不能一块，偶数和偶数不能一块。所以我们把它们按奇偶分类，又注意到，考虑网络流。
- 对于偶数的：
- 对于奇数的：
- 对于,且是偶数,是奇数：
跑一遍最大流。如果最大流，求出分组。否则就不可能。
预处理质数，解决（其中是网络流的复杂度，又被称为玄学常数）
10.24upd 关于建图的具体思路 建图是一个很考验思维能力的过程。 首先我们注意到，每个数最多有两个数相邻，所以这个数和源点/汇点的连边容量为$$2$$，就代表它最多能通过两条边。而$$DFS$$的时候，就是通过连接的两条边判断相邻，然后判断顺序的。 然后，考虑到相邻两个数的和必须是质数，所以，不是所有的边都能流过去，必须只有质数才能流过去。所以我们判断两个数的和是否为质数，如果是质数那么就连一条容量为$$1$$的流过去。 我个人认为，虽然网络流建图就是个毒瘤，但是这个题还比较容易能理解。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
using namespace std;
namespace Flandre_Scarlet
{
class Graph
{
public:
int EdgeCount;
int head[M];
struct Edge
{
int To,Label;
int Next;
}Ed[2666666];
void clear()
{
MEM(head,-1);
MEM(Ed,-1);
EdgeCount=-1;
}
void AddEdge(int u,int v,int w)
{
++EdgeCount;
Ed[EdgeCount]=(Edge){v,w,head[u]};
head[u]=EdgeCount;
}
void AddFlow(int u,int v,int w)
{
AddEdge(u,v,w);
AddEdge(v,u,0);
}
int Start(int i){return head[i];}
int To(int i){return Ed[i].To;}
int Label(int i){return Ed[i].Label;}
int Next(int i){return Ed[i].Next;}
int Source,Sink;
int deep[N];
queue<int>Q,EmptyQ;
bool BFS()
{
Q=EmptyQ;
FK(deep);
Q.push(Source);
deep[Source]=1;
do
{
int u=Q.front();Q.pop();
for(int i=head[u];~i;i=Ed[i].Next)
{
int v=Ed[i].To;
if (deep[v]==0 and Ed[i].Label>0)
{
deep[v]=deep[u]+1;
Q.push(v);
}
}
}while(!Q.empty());
if (deep[Sink]==0) return 0;
return 1;
}
int DFS(int u,int MinFlow)
{
if (u==Sink) return MinFlow;
for(int i=head[u];~i;i=Ed[i].Next)
{
int v=Ed[i].To;
if (deep[v]==deep[u]+1 and Ed[i].Label!=0)
{
int d=DFS(v,min(MinFlow,Ed[i].Label));
if (d>0)
{
Ed[i].Label-=d;
Ed[i^1].Label+=d;
return d;
}
}
}
return 0;
}
int Dinic()
{
int ans=0;
while(BFS())
{
int d;
while(d=DFS(Source,0x3f3f3f3f))
{
ans+=d;
}
}
return ans;
}
}Nt;
int n,a[N];
void R1(int &x)
{
x=0;char c=getchar();int f=1;
while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=(f==1)?x:-x;
}
void Input()
{
R1(n);
F(i,1,n) R1(a[i]);
}
int primes[M],notp[M];
void Init()
{
int &cnt=primes[0];
int n=20000;
notp[1]=1;
F(i,2,n)
{
if (!notp[i]) primes[++cnt]=i;
for(int j=1;i*primes[j]<=n and j<=cnt;++j)
{
int u=primes[j];
notp[i*u]=true;
if (i%u==0) break;
}
}
}
vector<int> mp[M];
bool vis[M];
void DFS(int u,int tot)
{
mp[tot].push_back(u);
vis[u]=1;
Tra(i,u)
{
int v=__v;
if (vis[v]==1) continue;
if (v!=S and v!=T)
{
if (i%2==0 and Nt.Label(i) ==0) DFS(v,tot);
if (i%2==1 and Nt.Label(i^1)==0) DFS(v,tot);
}
}
}
void Soviet()
{
Init();
Nt.clear();
S=n+1,T=n+2;
F(i,1,n)
{
if (a[i]%2==0)
{
Nt.AddFlow(S,i,2);
}
else
{
Nt.AddFlow(i,T,2);
}
}
F(i,1,n) F(j,1,n)
{
if (a[i]%2==0 and a[j]%2==1 and !notp[a[i]+a[j]])
{
Nt.AddFlow(i,j,1);
}
}
int flow=Nt.Dinic();
if (flow==n)
{
FK(vis);
int tot=0;
F(i,1,n)
{
if (vis[i]==0)
{
DFS(i,++tot);
}
}
printf("%d\n",tot);
F(i,1,tot)
{
printf("%d",mp[i].size());
F(j,0,(int)mp[i].size()-1)
{
printf(" %d",mp[i][j]);
}
putchar('\n');
}
}
else
{
puts("Impossible");
}
}
Flan IsMyWife()
{
Input();
Soviet();
}
}
int main()
{
Flandre_Scarlet::IsMyWife();
getchar();getchar();
return 0;
}