题意：有一个n*m的矩阵，告诉了在每一行或者每一列安装大炮的代价，每一个大炮可以瞬间消灭这一行或者这一列的所有敌人，然后告诉了敌人可能出现的L个坐标位置，问如何安置大炮，使花费最小。如果一个敌人位于第r行c列，则他可以被第r行或者第c列的大炮消灭。
链接：http://poj.org/problem?id=3308
这题突然就让我想起来那个多校的那道多米诺骨牌的那个，几乎一样的模型，还不过要把权值改一下，因为权值是相乘，那么就吧权值改成相加，也就是用log去改变。
这样的话 如果坐标为x，y的点要被消灭，那么要么走x要么走y，这样的话就直接是一个二分图的形式了。一边是行，一边是列，用出现的点连边，就是最小点权模型，最小点权模型就是集合x点的点权做为s-x的边权（流量），y点的权值为y-t的边权，x-y的边权为无穷大，这样见图那么就可以用最大流搞。
这是我曾经看过的一个大神对于二分图边权覆盖的讲解。好像就是这道题。
求二分图顶点覆盖问题，都是转化为最小割问题去求解，转化方法如下：
建超级源S 和超级汇 T，假设二分图两个点集分别为 X 和 Y。X和Y原来的边容量设为INF，将S到X里每个点x连一条边，边权为x的点权，也可以看做覆盖点x的所有出边的花费(W-)，将Y里每个点y到T连一条边，边权为y的点权，也可以看做覆盖点y的所有入边的花费(W+)。这样求得最小割容量，即为原问题的解。
/************这是对这个转化方法的解释和证明，有兴趣的同学可以看看************/
X到Y的边权为INF，自然不会成为最小割中的边，那就只有可能是S到X和Y到T中的边，而：S到X中点x的边e1, 权为点x的点权，点x和Y中的所有临边e2，都需要受到e1的流量的限制，同样，X到Y中点y的所有边也会受到点y到T的容量限制。这样求得割就能保证覆盖掉所有的边。
我们可以用反证法证明一下：假设有边<x, y>没有被覆盖掉，则边<S, x>流量为0且边<y, T>流量为0，而<x, y>流量为INF，自然可以找到一条S到T的增流路径<S, x, y, T>，与以求得流为最大流相矛盾，则可以说明，在最大流的情况下，所有的边都已经被覆盖掉。
而最小割问题可以用最大流来解决，问题就变得简单了。
/****************************************************************************/
#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
const double maxn = 1000000.0;
int m,n,l;
double row[],col[];
struct edge
{
int u,v;
double cap,flow;
};
vector<edge>edges;
vector<edge>ed;
vector<int>g[],G[]; void addedge(int u,int v,double cap,double flow)
{
edges.push_back((edge){u,v,cap,flow});
edges.push_back((edge){v,u,,});
int m;
m = edges.size();
g[u].push_back(m-);
g[v].push_back(m-);
} void init(int n)
{
int i;
for(i = ;i <= n;i++)
{
g[i].clear();
}
edges.clear();
}
int vis[],dis[],cur[];
int bfs(int s,int t,int n)
{
memset(vis,,sizeof(vis));
queue<int>q;
q.push(s);
dis[s] = ;
vis[s] = ; while(!q.empty())
{
int u,v;
u = q.front();
q.pop();
for(int i = ;i < g[u].size();i++)
{
edge &e = edges[g[u][i]];
v = e.v;
if(!vis[v] && e.cap-e.flow > )
{
vis[v] = ;
dis[v] = dis[u] +;
q.push(v);
}
}
}
return vis[t];
}
double dfs(int u,double a,int t)
{
if(u == t || a == )
return a;
int v;
double flow = ,f;
for(int& i = cur[u]; i < g[u].size();i++)
{
edge &e = edges[g[u][i]];
v = e.v;
if(dis[u]+ == dis[v] &&(f = dfs(v,min(a,e.cap-e.flow),t)))
{
e.flow += f;
edges[g[u][i]^].flow -= f;
flow += f;
a -= f;
if(a == )
break;
}
} return flow;
}
double maxflow(int s,int t)
{
double flow = ;
while(bfs(s,t,t))
{
memset(cur,,sizeof(cur));
flow+=dfs(s,,t);
}
return flow;
} int main()
{
int i,j;
int t; while(~scanf("%d",&t))
{
while(t--)
{
scanf("%d %d %d",&n,&m,&l);
init(n+m+); for(i=;i <= n;i++)
scanf("%lf",&row[i]); for(i = ;i <= m;i++)
scanf("%lf",&col[i]); int u,v; for(i = ;i <= n;i++)
addedge(,i,log(row[i]),);
for(i = ;i <= m;i++)
addedge(n+i,n+m+,log(col[i]),); for(i = ;i <= l;i++)
{
int a,b;
scanf("%d %d",&a,&b);
addedge(a,n+b,maxn,);
} double ans = maxflow(,n+m+);
printf("%.4f\n",exp(ans));
}
} return ;
}
