ZOJ@2874題意：給一個(gè)n*m的網(wǎng)格，網(wǎng)格中某些位有敵人，現(xiàn)在可以在網(wǎng)格邊上的x軸或者y軸設(shè)置炮臺(tái)，x炮臺(tái)可以消滅所在列上的所有敵人，y炮臺(tái)可以消滅所在行上的所有敵人。現(xiàn)在給定修建x炮臺(tái),y炮臺(tái)的費(fèi)用，問如何設(shè)置炮臺(tái)，使得消滅所有敵人總費(fèi)用最少（總費(fèi)用為設(shè)置炮臺(tái)費(fèi)用之積）。
解法：最大流。首先對炮臺(tái)費(fèi)用求對數(shù)，使得總費(fèi)用之積轉(zhuǎn)化為之和。建圖：從源點(diǎn)連有向邊到x軸，邊的容量為在該處設(shè)置炮臺(tái)的費(fèi)用；y軸上的點(diǎn)連有向邊到匯點(diǎn)，邊容量為在該點(diǎn)設(shè)置炮臺(tái)的費(fèi)用；如果網(wǎng)格中點(diǎn)(x,y)處有敵人，則從x處連邊到y(tǒng)，邊的容量設(shè)置為無窮大。
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;
}