题意 ： 有一个n*m的矩阵，L个伞兵可能落在某些点上，这些点的坐标已知，需要在某些位置安上一些枪，然后每个枪可以将一行或者一列的伞兵击毙。把这种枪安装到不同行的行首、或者不同列的列首，费用都不同。现在已知把激光枪安装到任意位置的费用，总的花费为这些安装了激光枪的行列花费的乘积。
思路 ：就是一个最大流问题。Dinic我不会，用的白皮书上的EK算法，嗯，还行，这个建图比较麻烦，就是把行列分开，成为m+n+1个点。嗯，不废话了，还是把大神博客链接弄过来吧，各方面都讲得很详细。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <math.h> using namespace std; const int maxn = ;
const int INF = ;
double a[maxn],cap[maxn][maxn],flow[maxn][maxn] ;
double f ;
int p[maxn] ;
int m,n,l; void EK(int s)
{
queue<int>Q ;
memset(flow,,sizeof(flow)) ;
f = ;
for( ; ; )
{
memset(p,-,sizeof(p)) ;
memset(a,,sizeof(a)) ;
a[s] = INF ;
Q.push(s) ;
while(!Q.empty())
{
int u = Q.front() ;Q.pop() ;
for(int v = ; v <= m+n+ ; v++)
{
if(!a[v] && cap[u][v] > flow[u][v])
{
p[v] = u ;
Q.push(v) ;
a[v] = min(a[u],cap[u][v]-flow[u][v]) ;
}
}
}
if(a[m+n+] == ) break ;
for(int u = m+n+ ; u != ; u = p[u])
{
flow[p[u]][u] += a[m+n+] ;
flow[u][p[u]] -= a[m+n+] ;
}
f += a[m+n+] ;
}
}
int main()
{
int T;
scanf("%d",&T) ;
while(T--)
{
memset(cap,,sizeof(cap)) ;
f = ;
double s ;
int x,y ;
scanf("%d %d %d",&m,&n,&l) ;
for(int i = ; i <= m ; i++)
{
scanf("%lf",&s) ;
cap[][i] = log(s) ;
}
for(int i = m+ ; i <= m+n ; i++)
{
scanf("%lf",&s) ;
cap[i][m+n+] = log(s) ;
}
for(int i = ; i < l ; i++)
{
scanf("%d %d",&x,&y) ;
cap[x][m+y] = INF ;
}
EK() ;
printf("%.4f\n",exp(f)) ;
}
return ;
}