【2018SCUACM Wednesday 7 Gpha】

题目来源

A:UVA 11624

B:UVA 10054

C:UVA 11374

D:UVALive 5713

E:UVA 11324

解题报告

A:嵌套BFS,第一层BFS用来搜索人的位置,第二层BFS用来更新火的位置。每次搜索人的位置之前先更新火的位置,如果人走到了边缘那就是答案,搜不到答案就输出IMPOSSIBLE,否则输出答案。注意特判一开始就在边缘的情况,直接走一步就出去了,答案就是\(1\)。因为这个特判WA了好多次,自己还是需要好好反省一下了。

B:欧拉回路模板题。一个无向图存在欧拉回路的充要条件是每个点的度数一定是偶数(入度=出度),所以我们在读取数据的时候先记录每个点的度数,如果有某个点的度数是奇数点,那肯定不存在解。否则我们任取一点开始第一次\(DFS\),完毕之后如果还有点没有被访问过,说明这个图可能存在多个互不相连的环,这种情况下也不存在解。否则说明存在欧拉回路,这时我们开始第二次\(DFS\),每到一个点就删掉与这个点相连的边,从而使整个图变成一个更小的欧拉图,然后继续搜索这些边通向的点。同时每删一条边,将这条边压入栈中。最终的答案就是这个栈内的边依次出栈。

本题注意两个测试数据之间输出一行空格,而最后一个数据不输出一行空格!

C:最短路题目,使用\(Dijkstra\)+优先队列优化求解最短路。我们先求不使用快速票的最短路,记起点、终点分别为\(S\)与\(E\),\(F[x]\)为起点\(S\)到点\(x\)的最短路,\(G[x]\)为终点\(E\)到点\(x\)的最短路,\(T[x][y]\)为点\(x\)与点\(y\)间使用快速票的时间。那么对于某条边\(e\)相连的两点,最佳方案就是\(min(F[E],F[x]+G[y]+T[x][y],F[y]+G[x]+T[y][x])\)(其实根据题意\(T[x][y]=T[y][x]\),前面那么写更易于理解而已)。

于是,\(F\)与\(G\)可以分别通过以\(S\)、\(E\)为起点跑\(Dijkstra\)求得,由于要记录路径,所以转移的时候使用一个\(pre\)数组记录一下最短路径的点。同时根据最佳方案的表达式记录一下使用车票的地点。\(T[x][y]\)其实没必要存,我们读取的时候读一个处理一个就好。

最后打印答案的时候注意一下细节就好,行末不要有多余的空格,每组数据下面只能有一行多的空行,否则会\(PE\)到死……

D;最小瓶颈路问题。要求到\(\frac{A}{B}\)的最大值,注意到任意选取两个点,\(A\)是确定的,所以尽可能让\(B\)小,于是首先我们可以构造一颗最小生成树,来尽量让\(B\)小。然后对于选取的点对\(u,v\),由于它们已经在最小生成树上了,所以直接连接它们显然成环,于是\(u\)到\(v\)的路径中可任选一条边删除而不会影响连通性,显然删除\(u\)到\(v\)的路径中最大的边能让\(B\)最小,问题就转化成了最小瓶颈路问题。

因此,我们用\(maxLen\)来表示\(u,v\)间的最长边,\(maxLen\)可用\(LCA\)的思想求出:$$maxLen=max(maxLength(u,LCA(u,v)),maxLength(v,LCA(u,v)))$$

之后枚举点对\(u,v\),则有\(A=city[u].population+city[v].population\),\(B=totalEdgeLength-maxLen(u,v)\)

计算\(\frac{A}{B}\)并取其最大值即可。

PS:安利一篇讲各种生成树的拓展的博客,思路讲的还不错:关于生成树的拓展

 

E:强连通缩点+SPFA求最长路(不要问我为啥不用网上的动态规划……)。先跑一遍\(Tarjan\)缩点去环,将每个强连通分量中的点个数记录下来,作为通向这个强连通分量的边权,于是求最多的点数就转化为在缩点后的图中能走的最长距离了,也就是在一个\(DAG\)(有向无环图)中求带权值最长路了。我们将所有点与\(0\)号点相连,利用\(SPFA\)算法跑一遍最长路,记录距离的最大值就是答案。

另外,似乎用\(Dijkstra\)+优先队列只能跑最短路跑不了最长路……

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

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

留下你的评论

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

*