题目大意：
在一个n*m的格子地图上有l个外星人，有一种激光炮可以消灭他们，每当使用一次可以使某一行或某一列的外星人消失。但每使用一次都需要付一定的价钱。给出在每一行或每一列使用激光炮时需要的价格，问最少需要付多少才能消灭全部外星人。总价格是每一次使用价格的乘积。
解题思路：
这题看起来跟POJ3041差不多，但在这里增加了价格就不一样了。虽然建出来的图类似于一个二分图，但是在这里得用求最小割的办法来解决问题，也就建图的时候需要一个超级源点和超级汇点。
1、首先建图，超级汇点向坐标X依次建边，前向边的容量是在下表是X的那一行使用激光炮的价格取log（），（注1）后向边容量为零。同理建出向坐标Y到超级汇点的。
2、对于每一个外星人的坐标，建立相应X点到Y点的边，前向边容量无穷大，后向边容量为0。
3、然后使用Dinic算法求出最大流，也就是最小割容量。
4、用exp（） 求出最小花费，
注意：
1、因为求最大流或者最小割是一个求和的过程，如果最小花费是乘积需要对数转化。
2、注意double的精度问题。
下面是代码：
#include <stdio.h>
#include <string.h>
#include <queue>
#include <math.h>
using namespace std;
const int inf=1e8;
const int Maxn=1005;
const double eps = 0.00000001;
struct node
{
int v,next;
double w;
} edge[ Maxn*5];
int n,m,l,head[Maxn],cnt,deep[Maxn];
void init()
{
memset(head,-1,sizeof(head));
cnt=0;
}
double Eps(double x)
{
return fabs(x)<eps?0:x;
}
double min(double a,double b)
{
return a<b?a:b;
}
void addedge(int u,int v,double w)
{
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
cnt++;
edge[cnt].v=u;
edge[cnt].w=0;
edge[cnt].next=head[v];
head[v]=cnt;
cnt++;
}
bool bfs()
{
memset(deep,-1,sizeof(deep));
queue <int > q;
q.push(0);
deep[0]=0;
while(!q.empty())
{
int t=q.front();
q.pop();
int p=head[t];
while(p!=-1)
{
int v=edge[p].v;
if( deep[v]==-1&&Eps(edge[p].w)>0)
{
q.push(v);
deep[v]=deep[t]+1;
}
p=edge[p].next;
}
}
return deep[n+m+1]!=-1;
}
void does(int u,int v,double w)
{
int p =head[u];
while(edge[p].v!=v)
{
p=edge[p].next;
}
edge[p].w+=w;
}
double dfs(int src,double flow)
{
if(src==n+m+1)return flow;
double sum=0;
int p=head[src];
while(p!=-1)
{
int v=edge[p].v;
if(deep[v]==deep[src]+1&&Eps(edge[p].w)>0)
{
double tmp=dfs(v,min(flow-sum,edge[p].w));
sum+=tmp;
edge[p].w-=tmp;
does(v,src,tmp);
}
p=edge[p].next;
}
return sum;
}
double dinic()
{
double ans=0;
while(bfs())
{
ans+=dfs(0,inf);
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
double val;
int u,v;
init();
scanf("%d%d%d",&n,&m,&l);
for(int i=1; i<=n; i++)
{
scanf("%lf",&val);
addedge(0,i,log(val));
}
for(int i=1; i<=m; i++)
{
scanf("%lf",&val);
addedge(n+i,n+m+1,log(val));
}
for(int i=0; i<l; i++)
{
scanf("%d%d",&u,&v);
addedge(u,v+n,inf);
}
printf("%0.4f\n",exp(dinic()));
}
return 0;
}