【题意】：给出m*n的格子，每一行每一列都有一杆激光枪，每一杆激光枪都对应着一个费用。有l个士兵分布在格子里面，现在要消灭所有的士兵，问最少费用是多少？费用的计算是使用的枪的费用的乘积。
【题解】：这题跟poj 2125那题类似，对于在格子（i,j）的士兵，我们可以用i这一行的枪来消灭或者用j这一列的枪来消灭，加上费用最少这个约束条件，我们又想到了最小点权覆盖集这个模型。构图：源点s向第i行的枪连边，容量为使用该枪的费用；第j列的枪向t连边，容量为使用该枪的费用。对于在格子（i,j）的士兵，连边i->j，容量为inf。显然这样连边后，最小割就是最少费用。但这个问题的费用不是求和，而是求乘积，于是我们需要作一些转化，使求乘积转化为求和。数学好的人可能马上就想到了怎么做，没错，就是取对数。log（a）+ log（b）= log（a * b），只需要把每个枪的费用转化为log（cost），这样就可以转化成求和形式，最后的结果只需取ans = exp（maxflow）即可。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "cmath"
5 using namespace std;
6 #define maxn 105
7 #define maxm 100000
8 const int inf = 1 << 30;
9
10 int n, m, s, t, l;
11 int eh[maxn], cur[maxn], pre[maxn], dist[maxn], tot, cnt[maxn];
12 double low[maxn];
13
14 struct Edge {
15 int u, v;
16 double cap, flow;
17 int next;
18 }et[maxm];
19
20 void init() {
21 tot = 0;
22 memset(eh, -1, sizeof(eh));
23 }
24
25 void add(int u, int v, double cap, double flow) {
26 Edge e = {u, v, cap, flow, eh[u]};
27 et[tot] = e;
28 eh[u] = tot++;
29 }
30
31 void addedge(int u, int v, double cap) {
32 add(u, v, cap, 0), add(v, u, 0, 0);
33 }
34
35 double isap(int s, int t, int n) {
36 int u, v, now;
37 double flow = 0;
38 memset(dist, 0, sizeof(dist));
39 memset(cnt, 0, sizeof(cnt));
40 memset(low, 0, sizeof(low));
41 for(u = 0; u <= n; u++) cur[u] = eh[u];
42 u = s;
43 while(dist[s] < n) {
44 for(now = cur[u]; now != -1; now = et[now].next)
45 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1) break;
46 if(now != -1) {
47 cur[u] = pre[v] = now;
48 low[v] = min(low[u], et[now].cap - et[now].flow);
49 u = v;
50 if(u == t) {
51 for(; u != s; u = et[pre[u]].u) {
52 et[pre[u]].flow += low[t];
53 et[pre[u]^1].flow -= low[t];
54 }
55 flow += low[t], low[s] = inf;
56 }
57 } else {
58 if(--cnt[dist[u]] == 0) break;
59 dist[u] = n, cur[u] = eh[u];
60 for(now = cur[u]; now != -1; now = et[now].next)
61 if(et[now].cap - et[now].flow && dist[u] > dist[v = et[now].v] + 1)
62 dist[u] = dist[v = et[now].v] + 1;
63 cnt[dist[u]]++;
64 if(u != s) u = et[pre[u]].u;
65 }
66 }
67 return flow;
68 }
69
70 int main() {
71 int T;
72 double cost;
73 scanf("%d", &T);
74 while(T--) {
75 init();
76 scanf("%d%d%d", &m, &n, &l);
77 s = 0, t = n + m + 1;
78 for(int i = 1; i <= m; i++) {
79 scanf("%lf", &cost);
80 addedge(s, i, log(cost));
81 }
82 for(int i = 1; i <= n; i++) {
83 scanf("%lf", &cost);
84 addedge(i + m, t, log(cost));
85 }
86 for(int i = 1; i <= l; i++) {
87 int u, v;
88 scanf("%d%d", &u, &v);
89 addedge(u, m + v, inf);
90 }
91 double ans = isap(s, t, t - s + 1);
92 ans = exp(ans);
93 printf("%.4f\n", ans);
94 }
95 return 0;
96 }