floyd一开始思路想错了……还多加了一维? 题目背景 B地区在地震过后,所有村庄都造成了一定的损毁,而这场地震却没对公路造成什么影响。但是在村庄重建好之前,所有与未重建完成的村庄的...
floyd
洛谷 P3502 [POI2010]CHO-Hamsters 题解【字符串】【hash】【倍增】
这是一道字符串建模+图论的问题。 题目描述 Byteasar breeds hamsters. Each hamster has a unique name, consisting of lower case letters of the English alphabet. The ha...
洛谷 P1841 [JSOI2007]重要的城市 题解【floyd】【bitset】
bitset玄学完美优化复杂度? 题目描述 参加jsoi冬令营的同学最近发现,由于南航校内修路截断了原来通向计算中心的路,导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断...
洛谷 P2047 [NOI2007]社交网络 题解【最短路】【Floyd】
用floyd解决的最短路计数问题。 题目描述 在社交网络(social network)的研究中,我们常常使用图论概念去解释一些社会现象。不妨看这样的一个问题。在一个社交圈子里有n个人,人与人之间有不...
洛谷 P1078 NOIP2012普及组 文化之旅 题解【图论】
这个题是普及组少见的图论题,因为数据范围是\(n\le 100\),所以求最短路时可以用Floyd,比较方便。 一开始我做这个题时感觉这个排斥可以用并查集处理,因为访问过的文化不会再访问一遍,也相当于排斥了。但是题...