Codeforces - 739E Gosha is hunting

题目链接：Gosha is hunting

题目大意：我们有两种精灵球，每种精灵球对于每种精灵抓住的概率不同，对同一个精灵，同种精灵球只能用一个。

比较明显的费用流，但是由于浮点数没有考虑精度，TLE了几次。

考虑建图：对于两种精灵球，我们可以建立两个虚拟节点，用超级源点S指向精灵球，流量就是精灵球的个数，费用为0.然后精灵球指向每个精灵，流量为1，费用为0.

精灵指向汇点T，有两条边，流量都为1，一条费用为0，代表只使用了一种精灵球，一条费用为-p*q代表使用了两种精灵球。

最后跑一次最大费用流即可：

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2010,M=20010;
const double eps=1e-8;
int n,a,b,s,t,sa,sb,v[N],e[N];
double d[N],w[M],p[M];
int head[N],nex[M],to[M],flow[M],tot=1;
inline void ade(int a,int b,int c,double d){
	to[++tot]=b; flow[tot]=c; w[tot]=d; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,double d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
inline bool spfa(){
	for(int i=1;i<=t;i++)	d[i]=-9999999;
	queue<int> q;	q.push(s);	int vis[N]={0};	vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]+eps<d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				v[to[i]]=u; e[to[i]]=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]>-9999999;
}
inline double EK(){
	double res=0;
	while(spfa()){
		int mi=0x3f3f3f3f;
		for(int i=t;i!=s;i=v[i])	mi=min(mi,flow[e[i]]);
		for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;
		res+=mi*d[t];
	}
	return res;
}
signed main(){
	scanf("%d %d %d",&n,&a,&b);	s=0; sa=n+1; sb=n+2; t=n+3;
	add(s,sa,a,0);	add(s,sb,b,0);
	for(int i=1;i<=n;i++){
		scanf("%lf",&p[i]);	add(sa,i,1,p[i]);	add(i,t,1,0);
	}
	for(int i=1;i<=n;i++){
		double x;	scanf("%lf",&x);	add(sb,i,1,x);	add(i,t,1,-(p[i]*x));
	}
	printf("%.6lf\n",EK());
	return 0;
}