题意：一个矩阵，有的方格里有一些敌人，每行或每列都可以安放一架枪，每架枪都有一个花费，而且能消灭他所在的行或列的所有敌人，最后的花费为所有的枪花费的乘积。
乘积问题可以先取对数。转化成求和。
然后问题很像以前的一个二分匹配问题。把每一行加入到X集合。每一列加入到Y集合。则每一个外星人所在的（row,col）就连条边。求最小点覆盖。但是这个问题有权值。可以转化成KM或者最小割来求解。
最小割建图：
src 与每一行相连，权值为每行的花费。
en 与每一列相连,权值为每列花费。
假如外星人出现在(r,c)则连一条r -->c权值为inf的边。
1 // File Name: 3308.cpp 2 // Author: Missa 3 // Created Time: 2013/4/17 星期三 11:24:48 4 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include
q; 51 memset(d, 0, sizeof(d)); 52 d[st] = 1; 53 q.push(st); 54 while (!q.empty()) 55 { 56 int u = q.front();q.pop(); 57 for (int i = head[u]; i != -1; i = p[i].next) 58 { 59 if (p[i].c > 0 && !d[p[i].v]) 60 { 61 d[p[i].v] = d[u] + 1; 62 q.push(p[i].v); 63 } 64 } 65 } 66 return d[en]; 67 } 68 double dfs(int u, double a) 69 { 70 if (u == en || fabs(a) <= eps) return a; 71 double f, flow = 0; 72 for (int& i = cur[u]; i != -1; i = p[i].next) 73 { 74 if (d[u] + 1 == d[p[i].v] && (f = dfs(p[i].v, min(a, p[i].c))) > 0) 75 { 76 p[i].c -= f; 77 p[i^1].c += f; 78 flow += f; 79 a -= f; 80 if (fabs(a) <= eps) break; 81 } 82 } 83 return flow; 84 } 85 double dinic(int st, int en) 86 { 87 double ret = 0, tmp; 88 while (bfs(st, en)) 89 { 90 for (int i = 0; i <= n; ++i) 91 cur[i] = head[i]; 92 ret += dfs(st, inf); 93 } 94 return ret; 95 } 96 int row, col, le; 97 int main() 98 { 99 int cas;100 double c;101 scanf("%d", &cas);102 while (cas--)103 {104 init();105 scanf("%d%d%d", &row, &col, &le);106 st = 0, en = row + col + 1;107 n = en;108 for (int i = 1; i <= row; ++i)109 {110 scanf("%lf", &c);111 addEdge(st, i, log(c));112 }113 for (int i = 1; i <= col; ++i)114 {115 scanf("%lf", &c);116 addEdge(i + row, en, log(c));117 }118 while (le--)119 {120 int u, v;121 scanf("%d%d",&u, &v);122 addEdge(u, v + row, inf);123 }124 printf("%.4f\n",exp(dinic(st, en)));125 }126 return 0;127 }