独立博客: 哲学与程序

哲学与程序

ZOJ@2874-Paratroopers

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;
}



posted on 2011-01-19 20:35 哲学与程序 阅读(269) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

公告

欢迎访问 http://zhexue.sinaapp.com

常用链接

随笔分类(37)

随笔档案(41)

Algorithm

最新随笔

搜索

最新评论

独立博客: 哲学与程序