CFR 510 E. Fox And Dinner ( Flow )

題意：
給長度 N 的數列 A[]。要求將每個元素分別放在某個圓桌裡，一個圓桌必須滿足以下條件：
每個元素和兩個元素相鄰。
相鄰元素的和必須是質數。

制約：
3 ≤ N ≤ 200
2 ≤ A[ i ] ≤ 1e4

解法：
和是質數，那麼偶數一邊，奇數一邊，二分圖問題。
源點到偶數元素建弧，容量為 2，代表要有兩個元素和它相鄰。
從奇數元素對匯點建弧，容量為 2。
對所有 ( 偶數, 奇數 )，其和為質數的對建弧，容量為 1，代標相同的對只能匹配一次。
如果滿流就一定有解，因為不可能會有一桌只有兩個人。

複雜度：
O( O( Dinic's ) )

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

template< class T >
struct Dinic {
  static const int MAXV = 10000;
  static const T INF = 0x3f3f3f3f;
  struct Edge {
    int v;
    T f;
    int re;
    Edge( int _v, T _f, int _re ): v( _v ), f( _f ), re( _re ) {}
  };
  int n, s, t, level[ MAXV ];
  vector< Edge > E[ MAXV ];
  int now[ MAXV ];
  Dinic( int _n, int _s, int _t ): n( _n ), s( _s ), t( _t ) {}
  void add_edge( int u, int v, T f, bool bidirectional = false ) {
    E[ u ].emplace_back( v, f, E[ v ].size() );
    E[ v ].emplace_back( u, 0, E[ u ].size() - 1 );
    if( bidirectional ) {
      E[ v ].emplace_back( u, f, E[ u ].size() - 1 );
    }
  }
  bool BFS() {
    memset( level, -1, sizeof( level ) );
    queue< int > que;
    que.emplace( s );
    level[ s ] = 0;
    while( not que.empty() ) {
      int u = que.front();
      que.pop();
      for( auto it: E[ u ] ) {
        if( it.f > 0 and level[ it.v ] == -1 ) {
          level[ it.v ] = level[ u ] + 1;
          que.emplace( it.v );
        }
      }
    }
    return level[ t ] != -1;
  }
  T DFS( int u, T nf ) {
    if( u == t ) return nf;
    T res = 0;
    while( now[ u ] < E[ u ].size() ) {
      Edge &it = E[ u ][ now[ u ] ];
      if( it.f > 0 and level[ it.v ] == level[ u ] + 1 ) {
        T tf = DFS( it.v, min( nf, it.f ) );
        res += tf; nf -= tf; it.f -= tf;
        E[ it.v ][ it.re ].f += tf;
        if( nf == 0 ) return res;
      } else ++now[ u ];
    }
    if( not res ) level[ u ] = -1;
    return res;
  }
  T flow( T res = 0 ) {
    while( BFS() ) {
      T temp;
      memset( now, 0, sizeof( now ) );
      while( temp = DFS( s, INF ) ) {
        res += temp;
        res = min( res, INF );
      }
    }
    return res;
  }
};

const int MAXN = 200;
const int MAXA = int( 1e4 );

int N;
int A[ MAXN ];
bool np[ MAXA * 2 + 1 ];

void dfs( int u, const Dinic< int > &din, bool *vis, vector< int > &table ) {
  for( int i = 0; i < din.E[ u ].size(); ++i ) {
    int v = din.E[ u ][ i ].v;
    if( v == din.s or v == din.t or vis[ v ] ) continue;
    if( A[ u ] & 1 ^ din.E[ u ][ i ].f ) continue;
    vis[ v ] = true;
    table.emplace_back( v );
    dfs( v, din, vis, table );
    return;
  }
}

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ) {
    cin >> A[ i ];
  }
  for( int i = 2; i <= MAXA * 2; ++i ) {
    if( np[ i ] ) continue;
    for( int j = i + i; j <= MAXA * 2; j += i ) {
      np[ j ] = true;
    }
  }
  int SOURCE = N, SINK = N + 1;
  Dinic< int > din( N + 2, SOURCE, SINK );
  for( int i = 0; i < N; ++i ) {
    if( A[ i ] & 1 ) {
      din.add_edge( i, SINK, 2 );
    } else {
      din.add_edge( SOURCE, i, 2 );
      for( int j = 0; j < N; ++j ) if( not np[ A[ i ] + A[ j ] ] ) {
        din.add_edge( i, j, 1 );
      }
    }
  }
  if( din.flow() != N ) cout << "Impossible\n", exit( 0 );
  vector< vector< int > > ans;
  for( int i = 0; i < N; ++i ) {
    static bool vis[ MAXN ];
    if( vis[ i ] ) continue;
    vis[ i ] = true;
    ans.emplace_back( vector< int >( 1, i ) );
    dfs( i, din, vis, ans.back() );
  }
  cout << ans.size() << endl;
  for( int i = 0; i < ans.size(); ++i ) {
    cout << ans[ i ].size() << " ";
    for( int j = 0; j < ans[ i ].size(); ++j ) {
      cout << ans[ i ][ j ] + 1 << " \n"[ j + 1 == ans[ i ].size() ];
    }
  }
  return 0;
}