Codeforces Round

传送门：https://codeforces.com/contest/512/problem/C

题意

有n个数，问能不能把n个数分成k桌，且要求如下

• 每桌至少3个数以上
• 一桌上相邻的数相加为素数

问能不能构造出k桌，能则输出，否则输出-1.

思路

题目要求相连的数相加为素数，我们知道，这两个数一定是一奇一偶。 而奇数相邻两个一定是偶数，偶数相邻两个一定是奇数。所以可以建立网络流模型。

先判断两个数相加是否为素数，是的话就将奇数向偶数连一条有向边，并且容量为1。 而这个奇数可以连接两个偶数，所以将源点向这个奇数连接一条有向边，容量为2。 同样，每个偶数都要向汇点连接一条有向边，容量为2。

跑一遍最大流，如果最大流=n，则是可以得到k桌。在残留网络上跑一遍DFS即可。

注意：n为奇数一定是不存在。

Code（30MS）

##include "bits/stdc++.h"
 using namespace std;

##define INF 0x3f3f3f3f

const int N = 405, M = 10005;
int n, m, s, t;
int maxflow;
int deep[N], cur[N];

struct Edge {
    int v, next, cap;
}e[M << 1];
int head[M << 1], cnt;

void init() {
    mem(head, -1);
    cnt = maxflow = 0;
}

inline void add(int u, int v, int cap) {
    e[cnt].v = v;
    e[cnt].cap = cap;
    e[cnt].next = head[u];
    head[u] = cnt++;

    e[cnt].v = u;
    e[cnt].cap = 0;
    e[cnt].next = head[v];
    head[v] = cnt++;
}

bool bfs() {
    for(int i = 0;i <= t; i++) {
        deep[i] = -1; cur[i] = head[i];
    }
    queue<int> q;
    q.push(s); deep[s] = 0;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            if(deep[v] == -1 && e[i].cap) {
                deep[v] = deep[u] + 1;
                q.push(v);
            }
        }
    }
    if(deep[t] >= 0) return true;
    else return false;
}

int dfs(int u, int mx) {
    int a;
    if(u == t) return mx;
    for(int i = cur[u]; ~i; i = e[i].next) {
        cur[u] = i;
        int v = e[i].v;
        if(e[i].cap && deep[v] == deep[u] + 1 && (a = dfs(v, min(mx, e[i].cap)))) {
            e[i].cap -= a;
            e[i ^ 1].cap += a;
            return a;
        }
    }
    return 0;
}

void dinic() {
    int res;
    while(bfs()) {
        while(1) {
            res = dfs(s, INF);
            if(!res) break;
            maxflow += res;
        }
    }
}

const int maxn = 4e4 + 10;
bool is_prime[maxn];
void sieve() {
    for(int i = 2;i < maxn; i++) {
        if(!is_prime[i]) {
            for(int j = i + i;j < maxn; j += i) {
                is_prime[j] = true;
            }
        }
    }
}

vector<int> ans[N];
bool vis[N];
int ver;

void DFS(int u) {
    vis[u] = 1;
    ans[ver].push_back(u); int v;
    for(int i = head[u]; ~i; i = e[i].next) {
        if(e[i].cap) continue;
        v = e[i].v;
        if(vis[v]) continue;
        vis[v] = 1;
        ans[ver].push_back(v);
        break;
    }
    for(int i = head[v]; ~i; i = e[i].next) {
        if(e[i ^ 1].cap) continue;
        v = e[i].v;
        if(vis[v]) continue;
        vis[v] = 1;
        DFS(v);
    }
}

vector<int> a(405);

void solve() {
    sieve();
    init();
    cin >> n;
    if(n & 1) {
        cout << "Impossible" << endl;
        return ;
    }
    s = 0; t = n + 1;
    for(int i = 1;i <= n; i++) {
        cin >> 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(!is_prime[a[i] + a[j]]) {
                if(a[i] & 1)
                    add(i, j, 1); // 奇数连接偶数
            }
        }
    }
    dinic();
    if(maxflow != n) {
        cout << "Impossible" << endl;
        return ;
    }
    for(int i = 1;i <= n; i++) {
        if(!vis[i] && (a[i] & 1)) {
            DFS(i); // 搜索每一桌
            ver++;
        }
    }
    cout << ver << endl;
    for(int i = 0;i < ver; i++) {
        cout << ans[i].size();
        for(int j = 0;j < ans[i].size(); j++) {
            cout << " " << ans[i][j];
        }
        cout << endl;
    }
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/02/05/codeforces-round-290-div-1-c/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！