最短路径 « Beyond the Void

NOI 2007 社交网络

这是NOI2007最简单的一道题了吧，考察的是细心。由于要求每对顶点的最短路径，可以用floyd求。定义path[i][j]为从i到j的最短路径的条数，floyd松弛时，要更新path[i][j] = path[i][k] * path[k][j]，如果...

题目要求是删除权值之和最少的一些边，使得从1到N的最短路径变大。方法是求最短路径网络上的最小割集。首先求出从1到N的最短路径网络，方法是分别从1和N求单源最短路径，然后枚举每...

这道题道德解法是离散化+染色+BFS最短路径。首先，由于坐标范围很大，离散化处理是很有必要的，这样可以把坐标范围从10000压缩到210以内。在离散化以后的格子中进行一次Floodfill，对每个...

前两问是最短路，第三问是标准的次短路径。求法是先求出最短路径，然后枚举每条从S到T的最短路径上的边，删除以后再求一次最短路径，保留最小值就是次短路径。

...

这道题不同于一般的次短路径问题，因为允许边重走。看似更为复杂了，其实是更简单了一些。方法为先用Heap+Dijkstra求出1和N的单源最短路径，把无向边看成两个有向边，然后枚举每单向条...

NOI1999的6道题分别是[钉子和小球][棋盘分割][生日蛋糕][最优连通子集][01串][内存分配]。六道题个题难易差别不太大，没有送分题，也没有特别困难的题。

[钉子和小球]是概率递推问题，...

这是NOI计划的第二份题解。NOI1998的6道题是[个人所得税][免费馅饼][围巾裁剪][SERNET模拟][软件安装盘][并行计算]，相对于NOI1997要稍难一些，不过还都是可以接受的。

[个人所得税]是一个...