POJ 3308 - Paratroopers

ACM POJ 解题报告
算法
原创
发布日期:   2011-10-03
更新日期:   2026-11-06
文章字数:   3.4k
阅读时长:   15 分
阅读次数:  

0x00 POJ 原题

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 m × n grid 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 r_(i) (resp. c_(i) ) 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 r_(i) and then, a line with n positive real numbers greater or equal to 1.0 comes where the ith number is c_(i). 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

0x10 题目概述

火星人侵略地球，他们意图登陆破坏某个地区的兵器工厂。据探子回报，火星人登陆的地区为 n*m 大小的地域，而且每一个火星人的着陆点坐标已知。

火星人很强悍，只要有一个火星人着陆后能够幸存，他必定能毁坏这片区域的全部兵工厂。为了防止这种情况发生，必须保证在火星人着陆的一瞬间把他们全部同时杀死。

现在防卫队有一个激光枪，开一枪就能把 在同一行（或同一列）着陆的火星人全部杀死。但是这种激光枪的使用是有代价的，把这种激光枪安装到不同行的行首、或者不同列的列首，费用都不同。现在已知把激光枪安装到任意位置的费用，总的花费为这些安装了激光枪的行列花费的乘积。

问怎样安装激光枪才能在杀死所有火星人的前提下费用最少？

0x20 解题思路

Dinic 算法求解最大流问题。

这题和 POJ3041 是要求开枪的次数最少破坏全部陨石，而本题是要求开枪的花费最少杀死全部火星人，由于在不同位置开枪的代价不同，因此“花费最小不一定就是开枪次数最少”，这个要注意。

本题的模型是显然是一个二分图，并且是二分图中直观的顶点覆盖问题。

首先说说“覆盖”的大致概念：图 G 的一个顶点覆盖是由一些顶点构成的集合 Q∈V(G), 又 G 中有若干条边的集合 P∈E(G)，这些边均至少有一个端点在 Q 内，则 P 被 Q 顶点覆盖。

二分图中的顶点覆盖问题是，如果覆盖每个顶点需要付出不同的代价，也可以说是不同的花费，或称为点权（或为容量），那么问题可以描述成，在保证覆盖所有边的情况下，如何使得权和最小。

求二分图顶点覆盖问题，都是转化为最小割问题去求解，转化方法如下：

建超级源 S 和超级汇 T，假设二分图两个点集分别为 X 和 Y。X 和 Y 原来的边容量设为 INF，将 S 到 X 里每个点 x 连一条边，边权为 x 的点权，也可以看做覆盖点 x 的所有出边的花费 (W-)，将 Y 里每个点 y 到 T 连一条边，边权为 y 的点权，也可以看做覆盖点 y 的所有入边的花费 (W+)。这样求得最小割容量，即为原问题的解。

这是对这个转化方法的解释和证明：

X 到 Y 的边权为 INF，自然不会成为最小割中的边，那就只有可能是 S 到 X 和 Y 到 T 中的边，而：S 到 X 中点 x 的边 e1, 权为点 x 的点权，点 x 和 Y 中的所有临边 e2，都需要受到 e1 的流量的限制，同样，X 到 Y 中点 y 的所有边也会受到点 y 到 T 的容量限制。这样求得割就能保证覆盖掉所有的边。

我们可以用反证法证明一下：假设有边 <x, y> 没有被覆盖掉，则边 <S, x> 流量为 0 且边 <y, T> 流量为 0，而 <x, y> 流量为 INF，自然可以找到一条 S 到 T 的增流路径 <S, x, y, T>，与以求得流为最大流相矛盾，则可以说明，在最大流的情况下，所有的边都已经被覆盖掉。

而最小割问题可以用最大流来解决，问题就变得简单了。

而我们又知道，图 G 的最小割的容量，等于其最大流的流量，因此本题最终是转化为最大流问题求解。（据我所知，还没有直接求最小割的算法）

下面说说本题的详细解题过程：

0x21 1. 构造二分图

构造方法按照上述把“顶点覆盖问题转化为最小割问题”的方法去处理：

显然取行坐标为二分图的 X 集合，编号为 1~N，点权就是激光炮在第 i 行射一炮的费用 ri；列坐标为二分图的 Y 集合，编号为 N+1~N+M，点权就是激光炮在第 j 列射一炮的费用 cj。

然后建立超级源 S，编号为 0，超级汇 T，编号为 N+M+1。S 向 X 集合每个点都连一条正向弧，边容量为第 i 点的点权；Y 集合每个点都向 T 连一条正向弧，边容量为第 j 点的点权。而落有伞兵火星人的区域，表示该位置的 x 与 y 是连通的，则从 X 集合取该点与 Y 集合的对应点连一条正向弧，边容量为无限大 inf。

X 集合每个点到 S 的反向弧、T 到 Y 集合每个点的反向弧，落有火星人区域的 y 到 x 的反向弧，也都要连上边（这是为了后续的 Dinic 算法在增广链上调整流量之用），但边容量默认为 0，表示不连通。

0x22 2. 求解最小割

此时问题转化为最小割问题，因为图 G 的最小割的容量等于其最大流的流量，因此用求最大流的方法去求解。

但本题数据比较 BT，常规求最大流的方法（压入重标法）会 TLE，因此只能用相对更高效的 Dinic 算法。

循环：一次 BFS 对残余图分层，一次 DFS 在层次图上求一条增广链，调整最大流。

0x23 实现时的注意事项

0x24 1. double 精度的问题

本题有一句这样的话：the total cost of constructing a system firing all guns simultaneously is equal to the product of their costs.

其中 product 不是“产品”的意思，而是“乘积”的意思，英语差的同学建议查字典。

因此为了方便求最大流，应该首先对所有费用（点权）求一次自然对数，把乘法转变为加法。最后再对累加的最小费用求一次 exp，就是答案。

而自然对数 log 是 double 型的， double 精度在 15～16 位左右，那么本题的无限大 inf 和最小精度 eps 的差距就不能超过 15 位，否则精度问题会把你 WA 成 sb。

而又由于，eps 要开到输出小数位数两倍的原则（本题要求取到 4 位小数），那么 eps 在本题中开到 1e-8 就是很有必要的一件事情，所以相应的 inf 最多只能开到 1e8。（但其实呢，2 倍原则一般针对带有乘除法的浮点型问题，所以本题只开到 1e-5 或者 1e-6 亦可）

但注意本题中的另一个性质，取对数，任何数字取对数 log 之后就会变得很小（别告诉我你不知道 O(logN)的算法有多么快），所以这题的 inf 开的很小就好。（inf 开到 1e2 都能过，说明 poj 还比较仁慈，没有添加什么超 2^100 的数据。）

0x25 2. 存储问题

本题推荐用邻接链表存储，邻接矩阵不可能不超时的。还有，上面构图时已经提及过了，在把二分图构造为单源单汇网络流时，看似都是只有一个方向的有向边（正向弧），但其实反向弧也要用到的（Dinic 算法），因此往链表添加边 a->b 时，若不顺便添加边 b->a，必然会 WA。

0x26 3. poj 的 C++ 和 G++的问题

对于双精度输出，G++上面要用 %f，C++则用 %lf，否则 WA。

0x30 AC 源码

//Memory Time 
// 796K  47MS 

#include<iostream>
#include<cmath>
#include<queue>
using namespace std;

class Node
{
public:
    int id;
    class Node* next;
    Node():id(-1),next(0){}
};

class solve
{
public:
    solve(int n,int m,int l):N(n),M(m),L(l)
    {
        Initial();
        Input_Creat();
        Dinic();
        printf("%.4lf\n",exp(MinCost));
    }
    ~solve()
    {
        delete[] level;

        for(int i=0;i<=T;i++)
            delete[] cap[i];

        EmptyList();
    }

    double min(double a,double b) const{return a<b?a:b;}
    double inf() const{return 1e8;}
    double eps() const{return 1e-8;}
    double precision(double x) const{return fabs(x)<eps()?0:x;}

    void Initial(void);                    //申请存储空间并初始化
    void Input_Creat(void);                //输入并创建单源单汇网络

    void Dinic(void);                    //Dinic算法寻找最大流
    bool BFS(void);                        //对剩余图标号分层
    double DFS(int str,double flow);    //搜索增广链，修正最大流
                                        //str:搜索起点; flow:“关口点str”允许通过的最大流

    void AddEdge(int a,int b);            //向邻接链表加入双向弧a<->b (反向弧b->a容量默认为0)
    void DelLink(Node* p);                //释放以p为表头的整条链
    void EmptyList(void);                //释放邻接链表

protected:

    int N;                //行数(X点集)
    int M;                //列数(Y点集)
    int L;                //伞兵数量
    int S;                //超级源
    int T;                //超级汇
    Node** LinkHead;    //邻接链表表头

    double** cap;        //容量，在本题“费用”即“容量”
    int* level;            //层次图上各顶点的标号
    double MinCost;        //最小总费用

};

void solve::Initial(void)
{
    MinCost=0;
    S=0;
    T=N+M+1;

    LinkHead=new Node*[T+1];
    for(int i=0;i<=T;i++)
        LinkHead[i]=0;

    cap=new double*[T+1];
    for(int j=0;j<=T;j++)
    {
        cap[j]=new double[T+1];
        memset(cap[j],0,sizeof(double)*(T+1));    //初始化所有弧的容量为0（不连通）
    }

    level=new int[T+1];

    return;
}

void solve::Input_Creat(void)
{
    /*Temporary*/

    int i,j,k;
    double R_cost,C_cost;
    int x,y;

    /*输入行费用，构造超级源S到X点集的边*/

    for(i=1;i<=N;i++)
    {
        scanf("%lf",&R_cost);
        cap[S][i]=log(R_cost);    //正向弧容量，取对数，化乘为加
        AddEdge(S,i);
    }

    /*输入列费用，构造Y点集到超级汇T的边*/

    for(j=N+1;j<T;j++)
    {
        scanf("%lf",&C_cost);
        cap[j][T]=log(C_cost);    //正向弧容量，取对数，化乘为加
        AddEdge(j,T);
    }

    /*输入伞兵的坐标，构造X点集到Y点集的边*/

    for(k=1;k<=L;k++)
    {
        scanf("%d %d",&x,&y);
        cap[x][y+N]=inf();        //正向弧容量
        AddEdge(x,y+N);
    }

    return;
}

void solve::AddEdge(int a,int b)
{
    /*正向弧部分*/

    if(!LinkHead[a])
        LinkHead[a]=new Node;

    Node* p1=LinkHead[a]->next;
    Node* pa=new Node;
    pa->id=b;
    pa->next=p1;
    LinkHead[a]->next=pa;

    /*反向弧部分*/

    if(!LinkHead[b])
        LinkHead[b]=new Node;

    Node* p2=LinkHead[b]->next;
    Node* pb=new Node;
    pb->id=a;
    pb->next=p2;
    LinkHead[b]->next=pb;

    return;
}

void solve::Dinic(void)
{
    while(BFS())
        MinCost+=DFS(S,inf());

    return;
}

bool solve::BFS(void)
{
    for(int i=S;i<=T;i++)
        level[i]=-1;

    queue<int>q;
    q.push(S);
    level[S]=0;

    while(!q.empty())
    {
        int a=q.front();
        if(LinkHead[a])
        {
            for(Node* p=LinkHead[a]->next;p;p=p->next)
            {
                int b=p->id;
                if(level[b]==-1 && precision(cap[a][b])>0)
                {
                    q.push(b);
                    level[b]=level[a]+1;
                }
            }
        }
        q.pop();
    }
    return level[T]!=-1;
}

double solve::DFS(int str,double flow)
{
    if(str==T)
        return flow;
                        //假设关口点str有多个分支
    double SubFlow=0;    //则SubFlow为前k个分支允许通过的最大流之和
                        //flow-SubFlow即为str能够给余下的分支所提供的最大流量之和

    if(LinkHead[str])
    {
        for(Node* p=LinkHead[str]->next;p;p=p->next)
        {
            int end=p->id;
            /*注意不能“跨层”搜索*/
            if(level[end]==level[str]+1 && precision(cap[str][end])>0)
            {
                double AdjustFlow=DFS(end,min(flow-SubFlow,cap[str][end]));
                SubFlow+=AdjustFlow;

                cap[str][end]-=AdjustFlow;    //正向弧容量修正
                cap[end][str]+=AdjustFlow;    //反向弧容量修正
            }
        }
    }

    return SubFlow;
}

void solve::DelLink(Node* p)
{
    if(p->next)
        p=p->next;
    delete[] p;
    return;
}

void solve::EmptyList(void)
{
    for(int i=1;i<=N;i++)
        if(LinkHead[i])
            DelLink(LinkHead[i]);
    return;
}

int main(void)
{
    int test;
    scanf("%d",&test);
    for(int t=1;t<=test;t++)
    {
        int n,m,l;
        scanf("%d %d %d",&n,&m,&l);
        solve poj3308(n,m,l);
    }
    return 0;
}

相关资料

文章作者: EXP
文章链接: https://exp-blog.com/algorithm/poj/poj3308-paratroopers/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
ACM POJ 解题报告
赏
  目录