Fox And Dinner(Codeforces 512 C)

不难发现是奇偶交替的,所以是个二分图。

然后环上每一个数贡献两次,因此在网络流上,起点向 $a_i$ 为奇数连流量为2的边 $(S,i)$,同理,偶数也一样。

然后 $(a_i,a_j)$ 最多贡献一次,所以 $(i,j)$ 流量为 $1$ 。

然后跑网络流,如果边有流,那就说明匹配了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>

using namespace std;

const int N = 505, M = 4e4 + 5;

struct edge { int y, c, next; } a[M << 1]; int len, last[N];
int q[N], d[N], gap[N], cur[N], T, S, n, m, val[N], prime[M]; 
vector<int> e[N], vec[N]; bool v[M]; int tmp, cnt; bool vis[N];

void gp() {
    for (int i = 2; i <= 20000; ++i) {
        if (!v[i]) prime[++m] = i;
        for (int j = 1; j <= m && i * prime[j] <= 20000; ++j) {
            v[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

void ins(int x, int y, int c) {
    a[++len] = (edge) { y, c, last[x] }; last[x] = len;
    a[++len] = (edge) { x, 0, last[y] }; last[y] = len;
}

void bfs() {
    memset(d, 0, sizeof d); memset(gap, 0, sizeof gap);
    memcpy(cur, last, sizeof cur); int l = 1, r = 0; ++gap[d[q[++r] = T] = 1];
    for (int x = q[l]; l <= r; x = q[++l]) 
        for (int k = last[x], y; k; k = a[k].next) 
            if (!d[y = a[k].y]) ++gap[d[q[++r] = y] = d[x] + 1];        
}

int ISAP(int x, int f) {
    if (x == T) return f;
    int s = 0, t; 
    for (int &k = cur[x], y; k; k = a[k].next) 
        if (d[y = a[k].y] == d[x] - 1) {
            s += (t = ISAP(y, min(f, a[k].c)));
            f -= t; a[k].c -= t; a[k ^ 1].c += t;
            if (!f) return s;
        }
    if (!(--gap[d[x]])) d[s] = T + 1;
    ++gap[++d[x]]; cur[x] = last[x];
    return s;
}

void dfs(int x, vector<int> &V) {
    vis[x] = 1; V.push_back(x);
    for (int k = last[x], y; k; k = a[k].next) {
        if (vis[y = a[k].y]) continue;
        if (val[x] & 1) {
            if (!a[k].c) ++a[k].c, dfs(y, V);
        }
        else {
            if (a[k].c) a[k].c = 0, dfs(y, V);
        }
    }
}

int main() {    
    scanf("%d", &n); gp(); int s1 = 0, s0 = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val[i]);
        if (val[i] & 1) ++s1;
        else ++s0;
    }
    if (s0 != s1) { puts("Impossible"); return 0; }
    len = 1; memset(last, 0, sizeof last);
    S = 0, T = n + 1;
    for (int i = 1; i <= n; ++i) {
        if (val[i] & 1) ins(S, i, 2);
        else ins(i, T, 2);
    }
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j) 
            if (!v[val[i] + val[j]]) {
                if (val[i] & 1) ins(i, j, 1);
                else ins(j, i, 1);
            }
    bfs(); int ans = 0; cnt = 0;
    while (d[S] <= T) ans += ISAP(S,0x3f3f3f3f);
    if (ans != n) { puts("Impossible"); return 0; }
    vis[S] = vis[T] = 1;
    for (int i = 1; i <= n; ++i) if (!vis[i]) {
        dfs(i, vec[++cnt]);
    }
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; ++i) {
        printf("%d ", vec[i].size());
        int siz = vec[i].size();
        for (int j = 0; j <siz; ++j) 
            printf("%d ", vec[i][j]);
        puts("");
    }
    return 0;
}