poj 3308 Paratroopers 网络流
由于最后结果是相乘，所以先log一下，转化成想加。
然后点做边，行，列做点。最小权覆盖。
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>using namespace std;const int maxn=2e2+9;const double inf=1e20,epx=1e-4;int que[maxn],level[maxn];int head[maxn],lon;struct{ int next,to; double c;}e[maxn*maxn<<1];void edgeini(){ memset(head,-1,sizeof(head)); lon=-1;}void edgemake(int from,int to,double c){ e[++lon].c=c; e[lon].to=to; e[lon].next=head[from]; head[from]=lon;}bool makelevel(int s,int t){ memset(level,0,sizeof(level)); int front=1,end=0; que[++end]=s; level[s]=1; while(front<=end) { int u=que[front++];// cout<<u<<endl; if(u==t) return true; for(int k=head[u];k!=-1;k=e[k].next) { int v=e[k].to; if(!level[v]&&e[k].c>epx) { que[++end]=v; level[v]=level[u]+1; } } } return false;}double dfs(int now,int t,double maxf){ if(t==now) return maxf; double ret=0; for(int k=head[now];k!=-1;k=e[k].next) { int u=e[k].to; if(e[k].c>epx&&level[u]==level[now]+1) { double f=dfs(u,t,min(maxf-ret,e[k].c)); e[k].c-=f; e[k^1].c+=f; ret+=f; } } return ret;}double maxflow(int s,int t){ double ret=0; while(makelevel(s,t)) { ret+=dfs(s,t,inf); } return ret;}int main(){// freopen("in.txt","r",stdin); int T; scanf("%d",&T); while(T--) { edgeini(); int n,m,p; scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;i++) { double tmp; scanf("%lf",&tmp); tmp=log(tmp)/log(2.0); edgemake(0,i,tmp); edgemake(i,0,0); } for(int i=1;i<=m;i++) { double tmp; scanf("%lf",&tmp); tmp=log(tmp)/log(2.0); edgemake(n+i,n+m+1,tmp); edgemake(n+m+1,n+i,0); } for(int i=1,x,y;i<=p;i++) { scanf("%d%d",&x,&y); edgemake(x,y+n,inf); edgemake(y+n,x,0); } double ans=maxflow(0,n+m+1); printf("%.4lf\n",pow(2,ans)); } return 0;}