CF512C Fox And Dinner(二分图,最大流)

题目链接

CF

题意简述

给你 $n$ 个整数,需要将它们分成任意个至少包含 $3$ 个数的环,使得每相邻两个数加起来是一个质数。

判断是否有解,若有解输出任意一组解。

$3\le n\le 200$, 数的范围是 $[2,10^4]$。

简要做法

首先,由于每个数都大于等于 $2$,加起来是质数的必要条件是一奇一偶。

所以,如果把数看成点,相加得到质数看成边,就得到了一张二分图。

而题目的要求可以看作是每个点都匹配两个点。因为所有点度数都为 $2$ 的简单无向图一定是一个至少包含 $3$ 个点的环。

所以可以这样建图:源点到奇数,容量为 $2$;奇数到与其之和为质数的偶数,容量为 $1$;偶数到汇点,容量为 $2$。

如果最大流为 $n$ 就有解。输出方案就和普通的网络流输出方案差不多(可以参考代码)。

参考代码

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
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210;
const int W = 20010;

int n, a[N], p[W], tot;
bool np[W];

struct Flow
{
const int s = N - 2;
const int t = N - 1;

int head[N], nxt[N * N], to[N * N], edge[N * N], cnt;
queue<int> q;
bool vis[N];
int dep[N];

void add(int u, int v, int w)
{
nxt[++cnt] = head[u];
head[u] = cnt;
to[cnt] = v;
edge[cnt] = w;
}

void Add(int u, int v, int w)
{
add(u, v, w);
add(v, u, 0);
}

bool bfs()
{
memset(dep, -1, sizeof(dep));
dep[s] = 0;
q.push(s);

while (!q.empty())
{
int u = q.front();
q.pop();

for (int i = head[u]; i; i = nxt[i])
{
int v = to[i];
int w = edge[i];
if (w > 0 && dep[v] == -1)
{
dep[v] = dep[u] + 1;
q.push(v);
}
}
}

return ~dep[t];
}

int dfs(int u, int flow)
{
if (dep[u] == dep[t]) return u == t ? flow : 0;

int out = 0;

for (int i = head[u]; i && flow - out; i = nxt[i])
{
int v = to[i];
int w = edge[i];
if (dep[v] == dep[u] + 1)
{
int f = dfs(v, min(flow - out, w));
edge[i] -= f;
edge[i ^ 1] += f;
out += f;
}
}

return out;
}

int maxFlow()
{
int out = 0;
while (bfs()) out += dfs(s, N);
return out;
}

void init()
{
cnt = 1;

for (int i = 1; i <= n; ++i)
{
if (a[i] & 1) Add(s, i, 2);
else Add(i, t, 2);
}

for (int i = 1; i <= n; ++i)
{
if (!(a[i] & 1)) continue;
for (int j = 1; j <= n; ++j)
{
if (np[a[i] + a[j]]) continue;
Add(i, j, 1);
}
}
}

vector<int> cycle(int u)
{
vector<int> out(1, u);
vis[u] = true;
while (1)
{
bool flag = false;
for (int i = head[u]; i; i = nxt[i])
{
int v = to[i];
int w = edge[i];
if (((a[u] & 1) ^ (w > 0)) && v <= n && !vis[v])
{
vis[v] = flag = true;
out.push_back(v);
u = v;
break;
}
}
if (!flag) break;
}
return out;
}

void output()
{
vector<vector<int> > ans;
for (int i = 1; i <= n; ++i) if (!vis[i]) ans.push_back(cycle(i));
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); ++i)
{
printf("%d", ans[i].size());
for (int j = 0; j < ans[i].size(); ++j) printf(" %d", ans[i][j]);
puts("");
}
}
} flow;

int main()
{
for (int i = 2; i < W; ++i)
{
if (!np[i]) p[++tot] = i;
for (int j = 1; j <= tot && i * p[j] < W; ++j)
{
np[i * p[j]] = true;
if (i % p[j] == 0) break;
}
}

scanf("%d", &n);

for (int i = 1; i <= n; ++i) scanf("%d", a + i);

flow.init();

if (flow.maxFlow() != n)
{
puts("Impossible");
return 0;
}

flow.output();

return 0;
}