CFR 498 C. Array and Operations ( Flow )

Problem - 498C - Codeforces

題意：
給長度為 N 的數列 A[]。
有 M 筆操作：
u v：選一個 A[ u ] 和 A[ v ] 的公因數 g，進行 A[ u ] /= g, A[ v ] /= g，保證 ( u + v ) % 2 == 1
問最多能有幾次，你選的公因數 g 不為 1。

制約：
2 ≤ N ≤ 100
1 ≤ M ≤ 100
1 ≤ A[ i ] ≤ 1e9

解法：
u + v 是奇數這件事情明示了可以轉換成二分圖上的問題。
將下標為偶數的作為一邊的節點，奇數的作為另一邊的節點。
預處理所有值的質因數分解。
對於所有可能出現的質因數 v：
__對於偶數的一個點 x，從源點建弧，容量為可除以 v 的次數。
__對於奇數，對匯點，同理。
對於所有 ( 偶數, 奇數 ) 對建弧，容量為無限大。
最大流即所求。

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

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

template< class T >
struct Dinic {
  static const int MAXV = 120;
  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 = 100;
const int MAXM = 100;

int N, M;
int A[ MAXN ];
int I[ MAXM ], J[ MAXM ];

set< int > all_fac;

void update_fac( set< int > &bag, int v ) {
  int _ = v;
  for( int i = 2; i * i <= _; ++i ) {
    if( _ % i != 0 ) continue;
    bag.emplace( i );
    while( _ % i == 0 ) _ /= i;
  }
  if( _ != 1 ) bag.emplace( _ );
}

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < N; ++i ) {
    cin >> A[ i ];
    update_fac( all_fac, A[ i ] );
  }
  for( int i = 0; i < M; ++i ) {
    cin >> I[ i ] >> J[ i ];
    --I[ i ], --J[ i ];
    if( I[ i ] & 1 ) {
      swap( I[ i ], J[ i ] );
    }
  }
  long long ans = 0;
  for( int v: all_fac ) {
    int MAXNODE = 100;
    int SOURCE = MAXNODE;
    int SINK = MAXNODE + 1;
    Dinic< int > din( MAXNODE + 2, SOURCE, SINK );
    for( int i = 0; i < N; ++i ) {
      int cnt = 0;
      for( int j = A[ i ]; j % v == 0; j /= v, ++cnt ) ;
      if( i & 1 ) {
        din.add_edge( i, SINK, cnt );
      } else {
        din.add_edge( SOURCE, i, cnt );
      }
    }
    for( int i = 0; i < M; ++i ) {
      din.add_edge( I[ i ], J[ i ], din.INF );
    }
    ans += din.flow();
  }
  cout << ans << endl;
  return 0;
}