网络流/二分图最小点权覆盖
sigh……这题……TLE&RE了好几发
建一个二分图，左边的每个结点代表行，右边的代表列，如果在(i,j)这个位置有一个外星人，那么我们就连一条边 （左 i ->右 j），这样的话，求一个二分图最小点权覆盖即可。
为什么这样建图是对的？大家学过二分图应该知道点覆盖是啥吧……（至少学过最小点覆盖=最大匹配吧？）那么我们选了某一个点，比如我们选了左边的第 i 个点，这就表示我们在第 i 行建了一座激光炮，它能打到的外星人就是这个点连出去的所有边！也就是说对于每个外星人（每条边），它被打死（边被覆盖）当且仅当它所在行或列至少有一个方向有激光炮（它连接的两个端点至少有一个被选中），那么现在应该明白了吧= =我们就是要选出权值和最小的一组点，使得所有边都被覆盖。这个用网络流来做比较方便……（其实是我不会别的做法……）
那么我们现在知道了这是一个二分图的模型，那么怎么建网络流的图呢？对于每个左边的顶点，我们连s->i,w=r[i]，右边顶点连汇点t，边权（流量）同理。然后对于二分图中的边我们连（左->右，流量为INF），跑一个最大流（最小割）。（割掉某条边就表示选这个点，边权为INF表示不割它）
看到这里你可能会问，这样做是不对的吧？样例都过不了的……
其实……一开始我由于英语没学好……“product”的意思是乘积！！！也就是所有建造的激光炮的权值之积……sigh
辣么怎么算积的最大值呢？网络流不是只能算和的最大值吗？下面就是见证奇迹的时刻：对所有的权值取log，然后对最终答案取exp！这样就华丽丽地将求乘积最大转化为了求和最大。
Trick：这题是取了log的边权……所以在用Dinic增广的时候边界判定需要小心小心再小心。对于double类型的最大流我参考网上的代码重新写了一个模板……
之前在【当前结点是否无法再继续增广（dfs时）】这个地方蛋疼了好久……因为边界处理的不好各种TLE
然后是边集开小了……500×2的RE，500×3的AC……
Source Code
Problem: User: sdfzyhy
Memory: 760K Time: 0MS
Language: G++ Result: Accepted Source Code //POJ 3308
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,M=,INF=;
const double eps=1e-;
typedef long long LL;
/******************tamplate*********************/ int n,m,l;
double r[N],c[N];
struct edge{
int from,to;
double cap,flow;
};
struct Net{
edge E[M*];
int head[N],next[M*],cnt;
int Q[N];
int s,t,d[N],cur[N];
inline void add(int from,int to,double cap){
E[++cnt]=(edge){from,to,cap,};
next[cnt]=head[from];
head[from]=cnt;
E[++cnt]=(edge){to,from,,};
next[cnt]=head[to];
head[to]=cnt;
}
inline void init(){
cnt=;
n=getint();m=getint();l=getint();
s=; t=n+m+;
F(i,s,t) head[i]=;
F(i,,n){
scanf("%lf",&r[i]);
add(s,i,log(r[i]));
}
F(i,,m){
scanf("%lf",&c[i]);
add(i+n,t,log(c[i]));
}
int x,y;
F(i,,l){
x=getint(); y=getint();
add(x,y+n,INF);
}
}
bool mklevel(){
memset(d,-,sizeof d);
d[s]=;
int l=,r=-;
Q[++r]=s;
while(l<=r){
int x=Q[l++];
for(int i=head[x];i;i=next[i]){
edge&e=E[i];
if (d[e.to]==- && e.cap>e.flow){
d[e.to]=d[x]+;
Q[++r]=(e.to);
}
}
}
return d[t]!=-;
}
double dfs(int x,double a){
if (x==t) return a;
double flow=;
for(int &i=cur[x];i && flow<a;i=next[i]){
edge&e=E[i];
if (e.cap-e.flow> && d[e.to]==d[x]+){
double f=dfs(e.to,min(a-flow,e.cap-e.flow));
flow+=f;
e.flow+=f;
E[i^].flow-=f;
}
}
if (!flow) d[x]=-;
return flow;
}
double Dinic(){
double flow=;
while(mklevel()){
F(i,s,t) cur[i]=head[i];
flow+=dfs(s,INF);
}
return flow;
}
}G1; int main(){
#ifndef ONLINE_JUDGE
freopen("3308.in","r",stdin);
freopen("3308.out","w",stdout);
#endif
int T=getint();
while(T--){
G1.init();
printf("%.4f\n",exp(G1.Dinic()));
}
return ;
}