ZOJ@2874题意：给一个n*m的网格，网格中某些位有敌人，现在可以在网格边上的x轴或者y轴设置炮台，x炮台可以消灭所在列上的所有敌人，y炮台可以消灭所在行上的所有敌人。现在给定修建x炮台,y炮台的费用，问如何设置炮台，使得消灭所有敌人总费用最少（总费用为设置炮台费用之积）。
解法：最大流。首先对炮台费用求对数，使得总费用之积转化为之和。建图：从源点连有向边到x轴，边的容量为在该处设置炮台的费用；y轴上的点连有向边到汇点，边容量为在该点设置炮台的费用；如果网格中点(x,y)处有敌人，则从x处连边到y，边的容量设置为无穷大。
Code
// 2389416 2011-01-19 19:57:39 Accepted 2874 C++ 40 352 redsea
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#define MAXN 105
#define inf 1000000000.00
double map[MAXN][MAXN];
double flow[MAXN][MAXN];
double max_flow(int n,double mat[][MAXN],int source,int sink,double flow[][MAXN]){
int pre[MAXN],que[MAXN],p,q,t,i,j;
double d[MAXN];
double tmp;
if (source==sink) return inf;
for (i=0;i<n;i++)
for (j=0;j<n;flow[i][j++]=0);
for (;;){
for (i=0;i<n;pre[i++]=0);
pre[t=source]=source+1,d[t]=inf;
for (p=q=0;p<=q&&!pre[sink];t=que[p++])
for (i=0;i<n;i++)
if (!pre[i]&&(tmp=mat[t][i]-flow[t][i]))
pre[que[q++]=i]=t+1,d[i]=d[t]<tmp?d[t]:tmp;
else if (!pre[i]&&(tmp=flow[i][t]))
pre[que[q++]=i]=-t-1,d[i]=d[t]<tmp?d[t]:tmp;
if (!pre[sink]) break;
for (i=sink;i!=source;)
if (pre[i]>0)
flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
else
flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
}
tmp = 0;
for (i=0;i<n;tmp+=flow[source][i++]);
return tmp;
}
int main()
{
int T, n, m, l, s, t;
double x;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&m,&n,&l);
s = 0;
t = m+n+1;
for(int i = 0; i < n+m+2; i++)
for(int j = 0; j < n+m+2; j++)
map[i][j] = 0;
for(int i = 1; i <= m; i++){
scanf("%lf",&x);
map[s][i] = log10(x);
}
for(int i = m+1; i <= n+m; i++){
scanf("%lf",&x);
map[i][t] = log10(x);
}
for(int i = 0; i < l; i++){
int sx, sy;
scanf("%d%d",&sx,&sy);
map[sx][m+sy] = 10;
}
printf("%.4lf\n", pow(10.0, max_flow(n+m+2,map,s,t,flow)));
}
return 0;
}