POJ 3308 - Paratroopers


问题描述

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

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

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

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

解题思路

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的最小割的容量,等于其最大流的流量,因此本题最终是转化为最大流问题求解。(据我所知,还没有直接求最小割的算法


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

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,表示不连通。

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

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

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


注意

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 的数据。)

2、 存储问题

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

3、poj的 C++ 和 G++的问题

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

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
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 1696 - Space Ant POJ 1696 - Space Ant
POJ 1696 - Space Ant Time: 1000MS Memory: 10000K 难度: 初级 分类: 凸包 问题描述一只蚂蚁,只会向左转,现在给出平面上很多个点,求解一种走法, 能使得蚂蚁能经过的点最多,每个顶点该蚂蚁
2011-10-03
下一篇 
POJ 2706 - Connect POJ 2706 - Connect
POJ 2706 - Connect Time: 1000MS Memory: 65536K 难度: 中级 分类: 模拟法 问题描述一种类似围棋的游戏,有黑白两种颜色的棋子。 规定黑棋为先手,白棋为后手。 放下棋子A后,若A的8个马步方
2011-10-03
  目录