CFR 739 E. Gosha is hunting ( MCMF )
題意:
你有 A 個普通球,B 個超級球。
有 N 隻神奇寶貝。
對於第 i 隻神奇寶貝,如果用普通球,抓到的機率是 P[ i ]; 如果用超級球,抓到的機率是 U[ i ]。
對於同一隻神奇寶貝,兩種球都只能至多丟一次。
問最佳策略下,期望可以抓到幾隻。
制約:
2 ≤ N ≤ 2000
0 ≤ A, B ≤ N
解法:
左邊一排節點代表神奇寶貝,右邊兩種球。
思想上的瓶頸在,兩種球都丟要如何表示。
兩種球都丟而抓到的機率是 1 - ( 1 - P[ i ] ) * ( 1 - U[ i ] ) = P[ i ] + U[ i ] - P[ i ] * U[ i ]
可以發現,希望的是如果兩種球都丟,那麼要額外扣除 P[ i ] * U[ i ]。
這其實不難,因為兩個都丟的話會有兩單位的流量,所以流到匯點的弧設定成一個單位可以是免費的,但第二個單位就要支付那麼多。
複雜度:
O( N ** 2 )
#include <bits/stdc++.h> using namespace std; template< class TF, class TC > struct CostFlow { static const int MAXV = 2100; static constexpr TC INF = 1e9; struct Edge { int v, r; TF f; TC c; Edge( int _v, int _r, TF _f, TC _c ): v( _v ), r( _r ), f( _f ), c( _c ) {} }; int n, s, t, pre[ MAXV ], pre_E[ MAXV ], inq[ MAXV ]; TF fl; TC dis[ MAXV ], cost; vector< Edge > E[ MAXV ]; CostFlow( int _n, int _s, int _t ): n( _n ), s( _s ), t( _t ), fl( 0 ), cost( 0 ) {} void add_edge( int u, int v, TF f, TC c ) { E[ u ].emplace_back( v, E[ v ].size(), f, c ); E[ v ].emplace_back( u, E[ u ].size() - 1, 0, -c ); } pair< TF, TC > flow() { while( true ) { for( int i = 0; i < n; ++i ) { dis[ i ] = INF; inq[ i ] = 0; } dis[ s ] = 0; queue< int > que; que.emplace( s ); while( not que.empty() ) { int u = que.front(); que.pop(); inq[ u ] = 0; for( int i = 0; i < E[ u ].size(); ++i ) { int v = E[ u ][ i ].v; TC w = E[ u ][ i ].c; if( E[ u ][ i ].f > 0 and dis[ v ] > dis[ u ] + w + 1e-9 ) { // !!!!! pre[ v ] = u; pre_E[ v ] = i; dis[ v ] = dis[ u ] + w; if( not inq[ v ] ) { inq[ v ] = 1; que.emplace( v ); } } } } if( dis[ t ] == INF ) break; TF tf = INF; for( int v = t, u, l; v != s; v = u ) { u = pre[ v ]; l = pre_E[ v ]; tf = min( tf, E[ u ][ l ].f ); } for( int v = t, u, l; v != s; v = u ) { u = pre[ v ]; l = pre_E[ v ]; E[ u ][ l ].f -= tf; E[ v ][ E[ u ][ l ].r ].f += tf; } cost += tf * dis[ t ]; fl += tf; } return { fl, cost }; } }; const int MAXN = 2000; int N, A, B; double P[ MAXN ]; double U[ MAXN ]; signed main() { ios::sync_with_stdio( 0 ); cin >> N >> A >> B; for( int i = 0; i < N; ++i ) { cin >> P[ i ]; } for( int i = 0; i < N; ++i ) { cin >> U[ i ]; } CostFlow< int, double > mcmf( N + 2 + 2, N + 2, N + 2 + 1 ); mcmf.add_edge( N + 2, N, A, 0.0 ); mcmf.add_edge( N + 2, N + 1, B, 0.0 ); for( int i = 0; i < N; ++i ) { mcmf.add_edge( N, i, 1, -P[ i ] ); mcmf.add_edge( N + 1, i, 1, -U[ i ] ); mcmf.add_edge( i, N + 2 + 1, 1, 0.0 ); mcmf.add_edge( i, N + 2 + 1, 1, P[ i ] * U[ i ] ); } cout << fixed << setprecision( 7 ) << -mcmf.flow().second << endl; return 0; }