三十三测

第一题city,一开始还以为不知道Goat1是多少,后面算了算是1……所以呢，最烦的就是这个输入，它的空格是不定量的，所以一开始写了个判断函数，假如有两个间隔就是3部分，假如一个间隔，1个是数字就是1部分，否则就是2部分。但是后来连边的时候实在是不好动，还要判断啥的，所以早上就让哈希啥的弄成一大坨，十分烦。 下午着重改了这题，输入就是如果有两个换行，那么就到了下一个部分。当然咯，这会“吃掉”首字符，后面也吃掉就行了。还有当它是空格时~~（不知道为啥这数据行末行初都有长长的空格……）~~，然后用map映射一下，这样算最短路时也好搞一点。 没错，最难搞的输入完成了~~happy~~但是后面又出问题了。按照题解步骤： ``` 令位置i的最快的车速度为speed[i] 1．用floyd算出任意两个位置间的最短距离d[i,j] 2．如果Home到TrainStation没有路，输出'UNREACHABLE' 3．所有的位置i向其他的可达的位置j连一条边，权为1+d[i,j]*60/speed[i] 4．Home的值设成-1，其他的为无穷大 5．用Dijkstra算出Home到TrainStation的最短路。 ``` 完成1，然后2，继而把dij变成Floyd算,然后就没有爆时间但是WA了6个点呀!我……~~真就不知道这是为啥，一开始还以为理解错了反复调试还改了，但是发现没错，就是不知道Floyd算的答案和Dijkstra能有啥不一样的……~~ 第二题tro，用递归建树以后就一直在想啥容斥原理，然后一直弄硬是没做出个名堂来，看了题解后才知道，这用dp不就很香吗。先看看怎么dp。很明显f1,f2,f3分别代表绿、蓝、红，然后分析一下就出来了。 ``` Num[I] = 0 F1[I]=1，F2[I]=0，F3[I]=0 Num[I] = 1 F1[I]=Max(F2[L]+1,F3[L]+1) F2[I]=Max(F3[L],F1[L]) F3[I]=Max(F2[L],F1[L]) Num[I] = 2 F1[I]=Max(F2[L]+F3[R]+1,F3[L]+F2[R] +1) F2[I]=Max(F1[L]+F3[R],F3[L]+F1[R]) F3[I]=Max(F1[L]+F2[R],F2[L]+F1[R]) ``` 最后求最大值就好了。但是呢，现在问题是不知道子树位置。这也就dp一下就行了。 第三题为Dijkstra的变形，不仅是求最小环，而且这个环里至少要有三点。环我们不会求，但是最短路会求。所以就暴力枚举边，然后把它给删掉，求最短路即可。 第四题，多源最短路，然后枚举点进行堆优化Dijkstra呗，这复杂度为O（Tn^2logn），比spfa跑的还慢我佛了。所以题解中正确的算法竟然是？！广搜！！想一下，还真就复杂度更加快的，因为它不用枚举点了呀！