CFR 808 F. Card Game ( Flow, Binary Search )
題意:
你有 N 張卡。第 i 張卡有 P[ i ] 單位的力量,C[ i ] 單位的魔法性質,L[ i ] 的門檻。
你想組一個總力量不小於 K 單位的牌組,但是這些牌的門檻必須不超過你的等級,並且任意兩張的魔法性質總和不為質數。
你現在的等級是 1,問你至少要多少等級才能得到想要的牌組,無解輸出 -1。
制約:
1 ≤ N ≤ 100
1 ≤ K ≤ 1e5
1 ≤ P[ i ] ≤ 1000
1 ≤ C[ i ] ≤ 1e5
1 ≤ L[ i ] ≤ N
解法:
兩張總和不為質數明示了可以轉為二分圖上的問題,奇數一邊,偶數另一邊,暫時先不考慮 C[ i ] = 1 的存在。
預處理質數真偽表。
對答案二分搜,每次重新建圖,忽視那些門檻超過的卡片。
顯然,對於一個 X = C[ i ],若第 i 張卡片要被取,那麼所有 C[ i ] = X 的卡片也都該被取。
圖上的點代表魔法性質的數字,源點給每個偶數的連弧,容量是對應的力量總和; 每個奇數對匯點連弧,容量是對應的力量總和。
給每對總和為質數的點建弧,容量為無限大。
這時的最大流便是我們不能取得的最小分數,並且他的補集是能取的最大分數。
至於有 C[ i ] = 1 的情況,討論取或不取,但不要把它真的丟進圖裡面。
複雜度:
玄學。
聽說 Dinic's 在二分圖上的表現是 O( V * E**0.5 )
#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 ) { 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; } } return res; } }; const int SOURCE = 100; const int SINK = 101; const int MAXN = 100; const int MAXP = 1000; const int MAXC = int( 1e5 ); int np[ MAXC * 2 + 1 ]; // not prime int N, K; int P[ MAXN ], C[ MAXN ], L[ MAXN ]; int score( int lv ) { vector< int > ps( MAXC + 1 ); vector< int > dsctz; for( int i = 0; i < N; ++i ) { if( lv < L[ i ] ) continue; dsctz.emplace_back( C[ i ] ); if( C[ i ] == 1 ) { ps[ 1 ] = max( ps[ 1 ], P[ i ] ); } else { ps[ C[ i ] ] += P[ i ]; } } sort( dsctz.begin(), dsctz.end() ); dsctz.erase( unique( dsctz.begin(), dsctz.end() ), dsctz.end() ); auto id = [ & ]( int x ) { return lower_bound( dsctz.begin(), dsctz.end(), x ) - dsctz.begin(); }; Dinic< int > no_one( 102, SOURCE, SINK ), has_one( 102, SOURCE, SINK ); int bad1 = 0; for( int i = 2; i <= MAXC; ++i ) if( ps[ i ] ) { if( i & 1 ) { no_one.add_edge( id( i ), SINK, ps[ i ] ); has_one.add_edge( id( i ), SINK, ps[ i ] ); } else { no_one.add_edge( SOURCE, id( i ), ps[ i ] ); if( np[ i + 1 ] ) { has_one.add_edge( SOURCE, id( i ), ps[ i ] ); } else { bad1 += ps[ i ]; } } } for( int x: dsctz ) if( ~x & 1 ) { for( int y: dsctz ) if( y & 1 ) if( y != 1 ) { if( not np[ x + y ] ) { no_one.add_edge( id( x ), id( y ), no_one.INF ); has_one.add_edge( id( x ), id( y ), has_one.INF ); } } } int sum = accumulate( ps.begin() + 2, ps.end(), 0 ); return max( sum - no_one.flow(), sum - bad1 + ps[ 1 ] - has_one.flow() ); } signed main() { for( int i = 2; i <= MAXC * 2; ++i ) { if( np[ i ] ) continue; for( int j = i + i; j <= MAXC * 2; j += i ) { np[ j ] = 1; } } ios::sync_with_stdio( 0 ); cin >> N >> K; for( int i = 0; i < N; ++i ) { cin >> P[ i ] >> C[ i ] >> L[ i ]; } int lb = 0, ub = N + 1; while( ub - lb > 1 ) { int mid = lb + ub >> 1; ( score( mid ) < K ? lb : ub ) = mid; } cout << ( ub <= N ? ub : -1 ) << endl; return 0; }