题目大意
有两种球,分别有
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 ;
}
以上.
转载请注明原文地址: https://ju.6miu.com/read-999996.html