题目大意

有两种球，分别有 a,b 个。 现有 n 只精灵，每只精灵有两个概率p1,p2分别表示用第一种球捕抓成功的概率和用第二种球捕抓成功的概率。每种精灵最多只能分别用两种球抓一次。 求最优策略下的最大期望捕获只数。

Data Constraint n≤2000

题解

先分析一个精灵对答案的贡献：

如果不抓，贡献为0如果只用第一种抓，贡献为 p1 如果只用第二种抓，贡献为 p2 如果用两种抓，贡献为 1−(1−p1)(1−p2)=p1+p2−p1p2

如何分配可以考虑网络流。记两种球对应的结点分别是 A,B ， (u,v,c,cost) 表示一条 u→v 的边流量为 c ，费用为cost。 显然 (S,A,a,0),(S,B,b,0) 然后对于精灵 i ，有：

(A,i,1,p1)

(B,i,1,p2) (i,T,1,0) (i,T,1,−p1p2)

跑一遍最大费用流即可。

SRC

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std ; #define N 2000 + 10 #define M 20000 + 10 const double eps = 1e-8 ; bool vis[N] ; double Cost[M] ; int Node[M] , Next[M] , C[M] , Head[N] , tot = 1 ; double Dist[N] , P1[N] , P2[N] ; int D[10*M] , Pre[N] ; int n , A , B , S , T ; double ans ; void link( int u , int v , int w , double cost ) { Node[++tot] = v , Next[tot] = Head[u] , C[tot] = w , Cost[tot] = cost , Head[u] = tot ; Node[++tot] = u , Next[tot] = Head[v] , C[tot] = 0 , Cost[tot] = -cost , Head[v] = tot ; } bool SPFA() { int i = 0 , j = 1 ; for (int i = 1 ; i <= n + 3 ; i ++ ) Dist[i] = 1e9 ; D[1] = S ; Dist[S] = 0 ; vis[S] = 1 ; while ( i < j ) { i ++ ; int now = D[i] ; for (int p = Head[now] ; p ; p = Next[p] ) { if ( !C[p] ) continue ; if ( Dist[Node[p]] - (Dist[now] + Cost[p]) > eps ) { Dist[Node[p]] = Dist[now] + Cost[p] ; Pre[Node[p]] = p ; if ( !vis[Node[p]] ) { vis[Node[p]] = 1 ; D[++j] = Node[p] ; } } } vis[now] = 0 ; } return Dist[T] < 1e9 ; } int main() { scanf( "%d%d%d" , &n , &A , &B ) ; S = 0 , T = n + 1 ; link( S , n + 2 , A , 0 ) ; link( S , n + 3 , B , 0 ) ; for (int i = 1 ; i <= n ; i ++ ) scanf( "%lf" , &P1[i] ) ; for (int i = 1 ; i <= n ; i ++ ) scanf( "%lf" , &P2[i] ) ; for (int i = 1 ; i <= n ; i ++ ) { link( n + 2 , i , 1 , - P1[i] ) ; link( n + 3 , i , 1 , - P2[i] ) ; link( i , T , 1 , P1[i] * P2[i] ) ; link( i , T , 1 , 0 ) ; } while ( SPFA() ) { int Minv = 0x7FFFFFFF ; for (int x = T ; x != S ; x = Node[Pre[x]^1] ) Minv = min( Minv , C[Pre[x]] ) ; ans += (double)Minv * Dist[T] ; for (int x = T ; x != S ; x = Node[Pre[x]^1] ) { C[Pre[x]] -= Minv ; C[Pre[x]^1] += Minv ; } } ans = -ans ; printf( "%.4lf\n" , ans ) ; return 0 ; }

以上.