fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fi first
  6. #define se second
  7. #define task "test"
  8. #define maxn 1500
  9. #define MAXN 200005
  10. constexpr long long INF = 1e18;
  11.  
  12. int n,m,k,l,r,s,t,maxflow;
  13. vector<int> adj[maxn];
  14. int a[maxn], c[maxn][maxn], f[maxn][maxn], trace[maxn];
  15. bitset<MAXN> prime;
  16. struct info{
  17.     int u, v, w;
  18.     bool operator < (const info &o) const{
  19.         return w < o.w;
  20.     }
  21. };
  22. void sang(){
  23.     prime.set();
  24.     prime[0] = prime[1] = 0;
  25.     for(int i = 2; i * i < MAXN; i++){
  26.         if(prime[i]){
  27.             for(int j = i * i; j < MAXN; j += i){
  28.                 prime[j] = 0;
  29.             }
  30.         }
  31.     }
  32. }
  33. void bfs(){
  34.     fill(trace, trace + 2*n + 2, 0);
  35.     trace[s] = -1;
  36.     queue<int> q;
  37.     q.push(s);
  38.     while(!q.empty()){
  39.         int u = q.front();
  40.         q.pop();
  41.         for(int v : adj[u]) {
  42.             if(trace[v]) continue;
  43.             if(f[u][v] >= c[u][v]) continue;
  44.             trace[v] = u;
  45.             q.push(v);
  46.         }
  47.     }
  48. }
  49.  
  50. void incflow(){
  51.     int v = t;
  52.     int x = INT_MAX;
  53.     while(v != s){
  54.         int u = trace[v];
  55.         x = min(x, c[u][v] - f[u][v]);
  56.         v = u;
  57.     }
  58.     maxflow += x;
  59.     v = t;
  60.     while(v != s){
  61.         int u = trace[v];
  62.         f[u][v] += x;
  63.         f[v][u] -= x;
  64.         v = u;
  65.     }
  66. }
  67.  
  68. int main(){
  69.     ios::sync_with_stdio(false);
  70.     cin.tie(0);cout.tie(0);
  71.  
  72.     if(fopen(task".inp","r")){
  73.         freopen(task".inp","r",stdin);
  74.         freopen(task".out","w",stdout);
  75.     }
  76.  
  77.     sang();
  78.  
  79.     cin >> n >> m;
  80.  
  81.     for(int i = 1; i <= n; i++){
  82.         cin >> a[i];
  83.     }
  84.     s = 0, t = 2*n + 1;
  85.     if(m & 1){
  86.         for(int i = 1; i <= n; i++){
  87.             c[s][i] = 1;
  88.             adj[s].push_back(i);
  89.             adj[i].push_back(s);
  90.         }
  91.         for(int i = n + 1; i <= 2*n; i++){
  92.             adj[i].push_back(t);
  93.             adj[t].push_back(i);
  94.         }
  95.         for(int i = 1; i <= n; i++){
  96.             for(int j = i; j <= n; j++){
  97.                 if(i != j && prime[a[i] + a[j]]){
  98.                     c[i][j + n] = 1;
  99.                     c[j + n][t] = 1;
  100.                     adj[i].push_back(j + n);
  101.                     adj[j + n].push_back(i);
  102.                 }
  103.             }
  104.         }
  105.         do{
  106.             bfs();
  107.             if(trace[t]){
  108.                 incflow();
  109.             }
  110.         }while(trace[t]);
  111.         cout << maxflow;
  112.     }else{
  113.         int res;
  114.         cin >> res;
  115.  
  116.         for(int i = 1; i <= n; i++){
  117.             c[s][i] = 1;
  118.             adj[s].push_back(i);
  119.             adj[i].push_back(s);
  120.         }
  121.         for(int i = n + 1; i <= 2*n; i++){
  122.             adj[i].push_back(t);
  123.             adj[t].push_back(i);
  124.         }
  125.         vector<info> b;
  126.         for(int i = 1; i <= n; i++){
  127.             for(int j = i; j <= n; j++){
  128.                 if(i != j && prime[a[i] + a[j]]){
  129.                     b.push_back({i, j, abs(a[i] - a[j])});
  130.                     adj[i].push_back(j + n);
  131.                     adj[j + n].push_back(i);
  132.                 }
  133.  
  134.             }
  135.         }
  136.         sort(b.begin(),b.end());
  137.         int ans = 0;
  138.         l = 1, r = n >> 1;
  139.         while(l <= r){
  140.             int mid = (l + r) >> 1;
  141.             int max_diff = res / mid;
  142.             for(int i = 1; i <= n; i++){
  143.                 for(int j = 1; j <= n; j++){
  144.                     c[i][j + n] = 0;
  145.                     c[j + n][t] = 0;
  146.                 }
  147.             }
  148.             for(auto e : b){
  149.                 if(e.w <= max_diff){
  150.                     c[e.u][e.v + n] = 1;
  151.                     c[e.v + n][t] = 1;
  152.                 }else break;
  153.             }
  154.             maxflow = 0;
  155.             for (int i = 0; i <= 2 * n + 1; i++) {
  156.                 for (int v : adj[i]) {
  157.                     f[i][v] = 0;
  158.                     f[v][i] = 0;
  159.                 }
  160.             }
  161.             do{
  162.                 bfs();
  163.                 if(trace[t]){
  164.                     incflow();
  165.                 }
  166.             }while(trace[t]);
  167.             if(maxflow >= mid) {
  168.                 ans = mid;
  169.                 l = mid + 1;
  170.             }else r = mid - 1;
  171.         }
  172.         cout << ans;
  173.     }
  174.     return 0;
  175. }
  176.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fcyTd4
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!