628F - Bear and Fair Set ( Flow )
題意:
有人說:他有 N 個數字,範圍在 [ 1, B ]。
他告訴你 Q 個式子,第 i 個為:
[ 1, upTo[ i ] ] 之間有 quantity[ i ] 個數字。
除此之外,N 個數字 % 5 == [ 0 .. 4 ] 的數量是相等的。
問是否有可能。
制約:
5 ≤ N ≤ B ≤ 1e4, N % 5 == 0
1 ≤ Q ≤ 1e4
解法:
這也算是區間問題,離散端點處理。
左邊一排節點代表每一小節可能的數字範圍,右邊一排是 0 .. 4 代表餘數的數量。
左邊按照提示從源點流入相應的數量。
右邊那些節點各自流到匯點 N / 5 單位。
對於每個右邊節點 r,左邊的節點 [ L, R ] 對 r 建弧,容量是 [ L, R ] 中模 5 餘數為 r 的數量。
如果滿流就有解。
複雜度:
O( O( Dinic's ) )
#include <bits/stdc++.h> using namespace std; template< class T > struct Dinic { static const int MAXV = 200000; static constexpr T INF = 1e9; 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 ) { E[ u ].emplace_back( v, f, E[ v ].size() ); E[ v ].emplace_back( u, 0, 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 = int( 1e5 ); const int MAXQ = int( 1e5 ); int N, B, Q; int upTo[ MAXQ + 1 ], quantity[ MAXQ + 1 ]; int ord[ MAXQ ]; int cnt[ MAXN + 1 ][ 5 ]; signed main() { ios::sync_with_stdio( 0 ); cin >> N >> B >> Q; for( int i = 0; i < Q; ++i ) { cin >> upTo[ i ] >> quantity[ i ]; ord[ i ] = i; } upTo[ Q ] = B; quantity[ Q ] = N; ord[ Q ] = Q; ++Q; sort( ord, ord + Q, [ & ]( int i, int j ) { return upTo[ i ] < upTo[ j ]; } ); for( int i = 1; i <= MAXN; ++i ) { for( int j = 0; j < 5; ++j ) { cnt[ i ][ j ] = cnt[ i - 1 ][ j ] + ( i % 5 == j ); } } Dinic< int > din( Q + 5 + 2, Q + 5, Q + 5 + 1 ); for( int i = 0, last = 0, psum = 0; i < Q; ++i ) { if( last == upTo[ ord[ i ] ] and quantity[ ord[ i ] ] != psum ) cout << "unfair" << endl, exit( 0 ); if( quantity[ ord[ i ] ] < psum ) cout << "unfair" << endl, exit( 0 ); din.add_edge( Q + 5, ord[ i ], quantity[ ord[ i ] ] - psum ); for( int j = 0; j < 5; ++j ) { din.add_edge( ord[ i ], Q + j, cnt[ upTo[ ord[ i ] ] ][ j ] - cnt[ last ][ j ] ); } last = upTo[ ord[ i ] ]; psum = quantity[ ord[ i ] ]; } for( int i = 0; i < 5; ++i ) { din.add_edge( Q + i, Q + 5 + 1, N / 5 ); } cout << ( din.flow() == N ? "fair" : "unfair" ) << endl; return 0; }