• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ3308 – Paratroopers

    ACM-POJ EXP 158阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

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

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

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

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

    解题思路

    Dinic算法求解最大流问题

    这题和 POJ3041 非常相似,但却并不是一回事。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在层次图上求一条增广链,调整最大流。不懂Dinic的同学建议先去查阅相关资料,边学边做吧!


    注意

    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。

    转载请注明:EXP 技术分享博客 » POJ3308 – Paratroopers

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址