【2018SCUACM FurtherTraining 21 Dijkstra】

题目来源

A:UVA1665

B:UVA1667

C:UVA1078

D:UVA10537

E:UVA12661

F:UVA1279

解题报告

A:把每个点从1开始编号,则位于\((x,y)\)处的点编号就是\((x-1)*m+y\)。顺序来看的话就是不断分解块,而逆序来看就是不断联通块,所以我们不难想到逆序然后用并查集来做。先把所有点按照高度从高到低排好序,然后从最后一个询问开始处理,每次先看这个点是不是未被淹没,如果是,则先把它当成独立块,\(ans+1\)。而后扫描它周围的四个块,通过并查集判断连通性,如果周围块也没被淹没并且可以合并则\(ans-1\)。如果当前点被淹没了,由于高度已经降序排好,所以直接\(break\)处理下一个询问即可。处理下一个询问之前记得记录一下这个询问的\(ans\)。

D:反向\(Dijkstra\)求最短路就行了,注意反向的时候,由于计算的是“下一个点到当前点所需的花费”,所以是用当前点的种类(镇/村)来决定边权的,如果是村,很简单,边权是就是\(1\);如果是镇的话需要稍微思考一下,题目说的每\(20\)个收费\(1\),相当于每\(20\)个物品只能保留\(19\)个,于是从当前点推下一个点的货物时,应用\(19\)作为判断标准,即下一个点到当前点的花费(边权)为\(ceil(now\div 19)\)(\(ceil()\)为向上取整函数)。

至于输出字典序最小路径嘛……在更新的时候判断一下如果能更新最短路,则记录前驱;如果下一个点到当前点花费和当前点最小花费一样,就比较一下下一个点和现在的前驱谁小,选小的那个,最后从起点一路反推回去就是路径了。

E:带条件最短路,记到达一个点\(s\)的最早时间是\(dis[s]\),\(s\)前面有一条边\(e\),则对\(e\)来说剩下的可通过时间就是\(leftTime=e[i].openTime-dis[s]%(e[i].openTime+e[i].closeTime)\),如果\(leftTime\ge e[i].passTime\),则\(dis[e[i].to]=dis[s]+e[i].passTime\),否则需要再等到第二次开门时走,等待时间为:\(waitTime=leftTime+e[i].closeTime\),则\(dis[e[i].to]=dis[s]+waitTime+e[i].passTime\),一遍\(Dijkstra\)即可。

F:比较恶心的第一道题……基本思路:动态问题求解首先求静态解,再求状态改变条件从而调节解。

本题我们可以计算出每条边边长随时间变化的函数,为了去掉根号我们计边长平方随时间变化的函数。

对点\(u:(x_u,y_u,z_u,v_{ux},v_{uy},v_{uz})\)和点\(v:(x_v,y_v,z_v,v_{vx},v_{vy},v_{vz})\)来说,他们的相对位置为\(t:(v_x-u_x,v_y-u_y,v_z-u_z,v_{vx}-v_{ux},v_{vy}-v_{uy},v_{vz}-v_{uz})\),为简化则记为\(t:(x,y,z,v_x,v_y,v_z)\),不难得出这两点的距离就是\(({v_x}^2+{v_y}^2+{v_z}^2)t^2+2(xv_x+yv_y+zv_z)t+(x^2+y^2+z^2)\),可以看出,边长的平方是一个二次函数\(f(t)=at^2+bt+c\)。

再来想想状态改变的条件,假设我们已经有一个最小生成树\(T\)了,要调节最小生成树,必然有一个时间点\(t_0\),\(t_0\)前在\(T\)中的边\(u\)比不在\(T\)中的边\(v\)要短,\(t_0\)后\(v\)比\(u\)短,并且若\(u\)的两个端点连通集合\(S_1\)和\(S_2\),则\(v\)的两个端点也是连通集合\(S_1\)和\(S_2\)的,才能做到替换。

因此,我们可以首先求得最初的最小生成树,计算出边长的平方对时间\(t\)的函数,从而计算出边两两之间交替的时刻,按时间从小到大排序,依次按照上述规则替换即可。因为涉及到替换,所以要记录一下边\(i\)在\(MST\)中是第几条边以及\(MST\)中第\(k\)条边对应的边编号。

想法其实难度中上,重要的是细节多,特别是二次函数判断交替时刻的那个地方,仔细画画图想想到底是谁替换谁。

推荐一篇这道题讲的比较好的博客:https://www.cnblogs.com/jerryRey/p/4765722.html

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*