题意

敌人侵略r*c的地图。为了消灭敌人，可以在某一行或者某一列安置超级大炮。每一个大炮可以瞬间消灭这一行（或者列）的敌人。安装消灭第i行的大炮消费是ri。安装消灭第j行的大炮消费是ci现在有n个敌人，告诉你这n个敌人的坐标，让你同时消灭这些敌人，为你最小花费是多少。花费的定义：每个大炮消费的乘积。

思路

非常经典的最小点权覆盖集问题，同最大流建模就可以了，建模方法可见胡伯涛论文《最小割模型在信息学竞赛中的应用》。 这道题的模型转换成最小点权覆盖集的方法可见 . 这里的点权最大是乘积的，只要

对权值取对数就把乘法转换成加法了~~

代码

[cpp] #include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <string> #include <cstring> #define MID(x,y) ((x+y)/2) #define MEM(a,b) memset(a,b,sizeof(a)) #define REP(i, begin, m) for (int i = begin; i < begin+m; ++ i) using namespace std; const int MAXV = 1005; const int MAXE = 1005; const int oo = 0x3fffffff; template struct Dinic{ struct flow_node{ int u, v; T flow; int opp; int next; }arc[2*MAXE]; int vn, en, head[MAXV]; int cur[MAXV]; int q[MAXV]; int path[2*MAXE], top; int dep[MAXV]; void init(int n){ vn = n; en = 0; MEM(head, -1); } void insert_flow(int u, int v, T flow){ arc[en].u = u; arc[en].v = v; arc[en].flow = flow; arc[en].next = head[u]; head[u] = en ++; arc[en].u = v; arc[en].v = u; arc[en].flow = 0; arc[en].next = head[v]; head[v] = en ++; } bool bfs(int s, int t){ MEM(dep, -1); int lq = 0, rq = 1; dep[s] = 0; q[lq] = s; while(lq < rq){ int u = q[lq ++]; if (u == t){ return true; } for (int i = head[u]; i != -1; i = arc[i].next){ int v = arc[i].v; if (dep[v] == -1 && arc[i].flow > 0){ dep[v] = dep[u] + 1; q[rq ++] = v; } } } return false; } T solve(int s, int t){ T maxflow = 0; while(bfs(s, t)){ int i, j; for (i = 1; i <= vn; i ++) cur[i] = head[i]; for (i = s, top = 0;;){ if (i == t){ int mink; T minflow = 0x7fffffff; //要比容量的oo大 for (int k = 0; k < top; k ++) if (minflow > arc[path[k]].flow){ minflow = arc[path[k]].flow; mink = k; } for (int k = 0; k < top; k ++) arc[path[k]].flow -= minflow, arc[path[k]^1].flow += minflow; maxflow += minflow; top = mink; i = arc[path[top]].u; } for (j = cur[i]; j != -1; cur[i] = j = arc[j].next){ int v = arc[j].v; if (arc[j].flow && dep[v] == dep[i] + 1) break; } if (j != -1){ path[top ++] = j; i = arc[j].v; } else{ if (top == 0) break; dep[i] = -1; i = arc[path[-- top]].u; } } } return maxflow; } }; Dinic dinic; double r[55], c[55]; int main(){ //freopen("test.in", "r", stdin); //freopen("test.out", "w", stdout); int n, m, l; int t; scanf("%d", &t); while(t --){ scanf("%d %d %d", &n, &m, &l); dinic.init(n+m+2); REP(i, 1, n){ scanf("%lf", &r[i]); dinic.insert_flow(n+m+1, i, log(r[i])); } REP(i, 1, m){ scanf("%lf", &c[i]); dinic.insert_flow(i+n, n+m+2, log(c[i])); } REP(i, 1, l){ int u, v; scanf("%d %d", &u, &v); dinic.insert_flow(u, v+n, oo); } printf("%.4f\n", exp(dinic.solve(n+m+1, n+m+2))); } return 0; } [/cpp]