图论Test3(20171002)解题报告——蒟蒻XZY

蒟蒻:警察叔叔!就是那个出题人!听了我的算法就改数据来卡我!

警察:我从未见过有如此厚颜无耻之出题人!

T1

  • 期望得分:100分
  • 实际得分:100分

题目来源:POJ - 2186

题解:kosaraju强联通分量缩点后,设出度为0的点个数为cnt。如果cnt>1则直接输出0(因为任意两个出度为0的点互相不能到达,即不可能有点可以满足所有点都能到达它)。如果cnt=1,很显然,就是出度为0的那个强联通分量内的所有点。

代码:



T2

  • 期望得分:100
  • 实际得分:100

题目来源:HDU - 1598

题解:枚举最小生成树中最小边是哪条,然后生成最小生成树,输出所有最小生成树的最长边与最短边的差值中最小值

代码:



T3

  • 期望得分:30
  • 实际得分:100

题目来源:POJ - 1639

题解:显然我和kb是一模一样的错误解法。只是数据太水A了。错解就不说了。

正解是“最小 度限制 生成树”(注意断句)

具体算法思路是先把park删除,然后跑最小生成树。这时候图不一定联通了。我们设有M个联通块,那我们就让这M个联通块每个都连一条边到park使得图联通。对于每个联通块可能有多个边通向park,我们选择长度最小的那条。这时候我们得到了最小M度生成树。然后我们枚举所有链接park却没有用上的边,尝试联通它。因为联通它之后会导致生成树变成图(即多了1条边),我们就去枚举删除哪条边。因为我们要让总权值最小,所以我们要让删掉的边权值最大。寻找最大边可以用动态规划(dfs)解决。我们选择一条链接park却没有用上的边,使得这条边的权值减去删掉的边的权值最小,这样可以让答案变小得更多。至于删除的边,必须是删除后可以使得整个图具有树的性质的。假设我们链接了一条从park到i的边,那么我们删除的边显然在park到i的路径上。这里用很简单的动归解决。

重复这个过程,直到park出度为k或者答案已经不能更小为止。

代码:



T4

  • 期望得分:100
  • 实际得分:100

题目来源:POJ - 3463

题解:一开始想着写记忆化搜索,却想不出(我太弱了)。突然发现比最短路长1其实就是次短路,因此。。。我们可以用上A*算法(这个在我出的图论测试1中出现过)。

我们弄个优先队列,每次取出(“起点到这个点的路径长度”+“这个点到终点的最短路长度”)最小的点进行扩展。第一次扩展到终点就是最短路。第二次扩展到终点的时候可能是最短路(可能最短路不止1条),也可能是次短路。然后我们就这样一条一条路径数。因为这样子第i次扩展到终点时路径长度一定是排名第i的(长度相同的谁拍前面随便)。

然而。。。abs考场把这个做法报出来了!当着制杖出题人的面!

然后出题人就开始卡这种做法——因为这种做法当答案较大时就gg了。

然而道高一尺,魔高一丈,我猜测——zz出题人必然会搞很多重边,导致答案陡然增加!于是我加了一个优化:记录每条边重复的次数,也就是把所有的重边合并到一起,然后路径条数统计时就不一条一条数,而是将重边数乘起来。比如从1到2有两条重边,2到3有3条重边,那么1到3就有2×3=6种走法!

显然,zz出题人无法卡掉我了。

然而,处于好心,我把我的优化告诉了出题人!

于是他又临时决定卡我的优化!

但是由于时间问题与舆论压力,所以他就没有卡我了。

我就AC了。

代码: