题意：给出一个坐标系，这个接下来会有伞兵降落在这个坐标系内，每个伞兵有个坐标，现在地球的军队要使得伞兵降落在地上的一瞬间杀死他们，所以他们造了一些激光，这些激光可以杀死一整行或者一整列的伞兵，每行每列都有一个造激光的花费，最后的总花费就是所有激光造价的乘积，问造价最少是多少。
思路：首先我们不考虑他的总花费是激光造价的乘积，如果仅仅是和的话，那么这个问题很简单，就是求最小割，但是现在他的造价不是和，那么怎么转化呢。
这时候我们就想到了对数的性质，lg（a ） + lg（b） = lg（a * b）。可以知道，要使得a * b 最小，就是使得lg（a） + lg（b）最小，那么问题就可以转化了。
所以我们可以将每行每列的造价转化称对数，然后求一次最小割即可。
建图过程就不赘述了，很模版的建图。
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Max 2505
#define FI first
#define SE second
#define ll long long
#define PI acos（-1.0）
#define inf 0x3fffffff
#define LL（x） （ x 《 1 ）
#define bug puts（"here"）
#define PII pair<int,int>
#define RR（x） （ x 《 1 | 1 ）
#define mp（a,b） make_pair（a,b）
#define mem（a,b） memset（a,b,sizeof（a））
#define REP（i,s,t） for（ int i = （ s ） ; i <= （ t ） ; ++ i ）
using namespace std;
#define N 5000
int n , m , k ;
struct kdq{
int s , e , next ;
double l ;
}ed[N] ;
int head[N] , num ;
int S , T ;
void add（int s ,int e , double l ）{
ed[num].e = e ;
ed[num].l = l ;ed[num].next = head[s] ;
head[s] = num ++ ;
ed[num].e = s ;ed[num].l = 0 ;ed[num].next = head[e] ;
head[e] = num ++ ;
}
void init（）{
mem（head ,-1） ;num = 0 ;
}
int deep[N] ;
int qe[N] ;
int dinic_bfs（）{
mem（deep ,-1） ;
deep[S] = 0 ;
int h = 0 , t = 0 ;
qe[h ++ ] = S ;
while（h > t）{
int tmp = qe[t ++ ] ;
for （int i = head[tmp] ; ~i ; i = ed[i].next ）{
double l = ed[i].l ;
int e = ed[i].e ;
if（l > 0 && deep[e] == -1）{
deep[e] = deep[tmp] + 1 ;
qe[h ++ ] = e ;
}
}
}
return deep[T] != -1 ;
}
double dinic_dfs（int now ,double f）{
if（now == T）return f ;
double flow = 0 ;
for （int i = head[now] ; ~i ; i = ed[i].next ）{
int e = ed[i].e ;
double l = ed[i].l ;
if（deep[e] == deep[now] + 1 && l > 0 && （f - flow） > 0 ）{
double mm = min（l , f - flow） ;
double nn = dinic_dfs（e , mm） ;
flow += nn ;
ed[i].l -= nn ;
ed[i ^ 1].l += nn ;
}
}
if（flow < 1e-8）deep[now] = -2 ;
return flow ;
}
double dinic（）{
double flow = 0 ;
while（dinic_bfs（））{
flow += dinic_dfs（S, inf） ;
}
return flow ;
}
int main（） {
int tt ;
cin 》 tt ;
while（tt -- ）{
cin 》 n 》 m 》 k ;
init（） ;
T = n + m + 1 ;
for （int i = 1 ; i <= n ; i ++ ）{
double d ;
scanf（"%lf",&d） ;
add（S , i , log（d * 1.0）） ;
}
for （int i = 1 ; i <= m ; i ++ ）{
double d ;
scanf（"%lf",&d） ;
add（i + n , T , log（d * 1.0）） ;
}
for （int i = 0 ; i < k ; i ++ ）{
int x , y ;scanf（"%d%d",&x,&y） ;
add（x , y + n , inf） ;
}
printf（"%.4f\n",exp（dinic（））） ;//最后转化回来就可以了
}
return 0 ;
} |