【題意】：給出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 }