POJ 3308 Paratroopers

Description

It is year 2500 A.D. and there is a terrible war between the forces of the Earth and the Mars. Recently, the commanders of the Earth are informed by their spies that the invaders of Mars want to land some paratroopers in the × ngrid yard of one their main weapon factories in order to destroy it. In addition, the spies informed them the row and column of the places in the yard in which each paratrooper will land. Since the paratroopers are very strong and well-organized, even one of them, if survived, can complete the mission and destroy the whole factory. As a result, the defense force of the Earth must kill all of them simultaneously after their landing.

In order to accomplish this task, the defense force wants to utilize some of their most hi-tech laser guns. They can install a gun on a row (resp. column) and by firing this gun all paratroopers landed in this row (resp. column) will die. The cost of installing a gun in the ith row (resp. column) of the grid yard is ri (resp. ci ) and the total cost of constructing a system firing all guns simultaneously is equal to the product of their costs. Now, your team as a high rank defense group must select the guns that can kill all paratroopers and yield minimum total cost of constructing the firing system.

Input

Input begins with a number T showing the number of test cases and then, T test cases follow. Each test case begins with a line containing three integers 1 ≤ m ≤ 50 , 1 ≤ n ≤ 50 and 1 ≤ l ≤ 500 showing the number of rows and columns of the yard and the number of paratroopers respectively. After that, a line with m positive real numbers greater or equal to 1.0 comes where the ith number is ri and then, a line with n positive real numbers greater or equal to 1.0 comes where the ith number is ci. Finally, l lines come each containing the row and column of a paratrooper.

Output

For each test case, your program must output the minimum total cost of constructing the firing system rounded to four digits after the fraction point.

Sample Input

1
4 4 5
2.0 7.0 5.0 2.0
1.5 2.0 2.0 8.0
1 1
2 2
3 3
4 4
1 4

Sample Output

16.0000

Source

Amirkabir University of Technology Local Contest 2006

二分图最小点权覆盖集

对于一个敌人拆成两个点x,y

从S向x连给定权值的边,

从y向T连给定权值的边,

从x向y连INF的边

二分图最小点权覆盖集=最小割=最大流

乘法取log变加法

mmp精度坑死人

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#define AddEdge(x,y,z) add_edge(x,y,z),add_edge(y,x,0);
using namespace std;
const int MAXN=100001;
double INF=2000000000;
const double eps=1e-9;
int N,M,P,S,T;
struct node
{
    int u,v,nxt;
    double flow;
}edge[MAXN*5];
int head[MAXN],cur[MAXN],num=0;
inline void add_edge(int x,int y,double z)
{
    edge[num].u=x;
    edge[num].v=y;
    edge[num].flow=z;
    edge[num].nxt=head[x];
    head[x]=num++;
}
int deep[MAXN];
inline bool BFS()
{
    memset(deep,0,sizeof(deep));
    deep[S]=1;
    queue<int>q;
    q.push(S);
    while(q.size()!=0)
    {
        int p=q.front();
        q.pop();
        for(int i=head[p];i!=-1;i=edge[i].nxt)
            if(!deep[edge[i].v]&&edge[i].flow>eps)
            {
                deep[edge[i].v]=deep[p]+1;q.push(edge[i].v);
                if(edge[i].v==T) return 1;
            }
    }
    return deep[T];
}
double DFS(int now,double nowflow)
{
    if(now==T||nowflow<eps)    return nowflow;
    double totflow=0;
    for(int &i=cur[now];i!=-1;i=edge[i].nxt) 
    {
        if(deep[edge[i].v]==deep[now]+1&&edge[i].flow>eps)
        {
            double canflow=DFS(edge[i].v,min(nowflow,edge[i].flow));
            if(canflow>eps)
            {
                   edge[i].flow-=canflow;
                edge[i^1].flow+=canflow;
                   totflow+=canflow;
                   nowflow-=canflow;    
            }
            if(nowflow<eps) break;
        }
    }
    return totflow;
}
double Dinic()
{
    double ans=0;
    while(BFS())
    {
        memcpy(cur,head,sizeof(head)); 
        ans+=DFS(S,INF);
    }
    return ans;    
}
double valr,valc;
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    int test;
    scanf("%d",&test);
    while(test--)
    {
        memset(head,-1,sizeof(head));
        scanf("%d%d%d",&N,&M,&P);S=0;T=N+M+P;
        for(int i=1;i<=N;i++) scanf("%lf",&valr),AddEdge(S,i,log(valr) );
        for(int i=1;i<=M;i++) scanf("%lf",&valc),AddEdge(i+N,T,log(valc) );
        for(int i=1;i<=P;i++) 
        {
            int x,y;
            scanf("%d%d",&x,&y);
            AddEdge(x,y+N,INF);
        }
        printf("%.4lf\n",exp(Dinic()));
    }
    
    return  0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

HDUOJ------Lovekey

Lovekey Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (J...

2879
来自专栏数据小魔方

左手用R右手Python系列之——json序列化与反序列化

json格式数据作为如今越来越流行的数据交换格式,几乎已经成为web端数据交互的标准,主流的数据科学语言R,Python都中都有非常完善的半结构化数据与json...

3117
来自专栏数据结构与算法

P1967 货车运输

题目描述 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想...

3329
来自专栏数据结构与算法

3122 奶牛代理商 VIII

3122 奶牛代理商 VIII 时间限制: 3 s 空间限制: 256000 KB 题目等级 : 大师 Master 题目描述 Descripti...

3398
来自专栏数据结构与算法

BZOJ3277: 串(广义后缀自动机)

字符串是oi界常考的问题。现在给定你n个字符串,询问每个字符串有多少子串(不包括空串)是所有n个字符串中

1342
来自专栏十月梦想

js二维数组遍历

2042
来自专栏JetpropelledSnake

Django学习笔记之Django ORM Aggregation聚合详解

在当今根据需求而不断调整而成的应用程序中,通常不仅需要能依常规的字段,如字母顺序或创建日期,来对项目进行排序,还需要按其他某种动态数据对项目进行排序。Djngo...

1012
来自专栏ml

Java 基础知识点(必知必会其二)

   1.如何将数字输出为每三位逗号分隔的格式,例如“1,234,467”?    1 package com.Gxjun.problem; 2 3 i...

3865
来自专栏数据结构与算法

BZOJ4503: 两个串(bitset字符串匹配)

就是记录匹配串中每个元素出现的位置,将第\(i\)个位置的bitset右移\(i\)位后与起来

1071
来自专栏Albert陈凯

2018-04-17 Java的Collection集合类3分钟搞掂Set集合前言

3分钟搞掂Set集合 前言 声明,本文用的是jdk1.8 现在这篇主要讲Set集合的三个子类: HashSet集合 A:底层数据结构是哈希表(是一个元素为链...

2977

扫码关注云+社区

领取腾讯云代金券