[轉載]次短路径与次小生成树问题的简单解法

轉載自http://www.byvoid.com/blog/2-sp-mst/ ，轉載請註明！

  次短路径与次小生成树问题的简单解法

 

[次短路径]

次短路径可以看作是k短路径问题的一种特殊情况，求k短路径有Yen算法等较为复杂的方法，对于次短路径，可以有更为简易的方法。下面介绍一种求两个顶点之间次短路径的解法。

【精華轉載】因為我們是OIer！

我們是OIer，

所以我們
不用在跑道上揮汗如雨；
不用在球場上健步如飛；
更不用在沒事的時候，
經受非人的體能訓練……
但是，
我們卻要把頭腦
高速運轉，
還要接受一大堆
大學生也只是
“瞭解即可”的知識，
把一個個抽象的問題
轉化為一篇篇
優美的代碼，
才能在F9按下以後
獲得歡呼。
不要以為我們
機房裡沒有風吹，
沒有日曬，
就比勤勞的體育生們輕鬆，
只不過是大腦和四肢
的區別罷了。
可是，
OIer的寂寞和委屈又有誰能懂？
自習課鏖戰機房，
卻被認為而是逃課上網；
為榮耀耽誤考試去比賽，
卻被認為是逃避。
體育的同學們雖然辛苦，
但在揮汗如雨的背後，
有人在喝彩鼓掌；
在風吹日曬的同時，
有粉絲在仰慕。
而我們呢？
與UnAC較勁的時候，
只有那一遍遍的運行窗口，
知道我們的不屈；
刷題的漫漫長夜，
只有陪伴我們的筆記本電腦，
知道我們的不懈；
在自習課別人學習的時候，
只有板磚般的算法導論，
知道我們的進取；
在機房泡得搶不上飯的時候，
只有五毛一包的乾脆面，
知道我們的執著……
沒有人會理解，
OIer見面，
除了程序、算法之外
別無他言。
我們的世界裡，
從來不會有遊戲、歌星的出現。
這不是被家長逼迫的“小三門”，
是我們的興趣，
我們的愛好，
乃至我們的事業。
每一個OIer都幻想著
自己脖子上可以
掛上一塊沉甸甸的金牌，
而不是
萬惡的應試教育的枷鎖。
沒準哪個OIer，
就是下一個艾倫•圖靈，
挑戰頭腦的極限，
去做最不平凡的自己。。。。。。

【精華轉載】假如沒有OI

假如沒有OI，我會像其他大多數人一樣擡頭看天，低頭看書，安靜的過完整個高中
假如沒有OI，我會一個人，一邊寫著作業，一邊做著肥皂般繁華的夢
假如沒有OI，我會輕鬆地擠進學校前100名，然後衣食無憂地等著高考地到來
假如沒有OI，我可以只用一半自習課的時間寫完所有作業，而不是晚上熬到深夜
假如沒有OI，我從來都不會知道矩陣，行列式，容斥原理等原本不屬於我們這個年齡的東西
假如沒有OI，我會花錢買一本《人間詞話》，而不是板磚一樣的《C++ primer》
假如沒有OI，我的空間裡會有一篇篇自己寫的詩或散文，而不是一堆解題報告
假如沒有OI，我永遠也不會聽說OIER這個名詞，也永遠不會去RQNOJ，BYVoid等網站
假如沒有OI，我在學校最常去的地方是圖書館，而不是機房
假如沒有OI，我的電腦裡會塞滿遊戲，而不是裝著IDE，編譯器和一包包的測試資料
假如沒有OI，我每天都會有大把的時間可以去放肆地揮霍
假如沒有OI，我永遠也不知道”犇“的讀音
假如沒有OI，我可能不會知道夢的含義，還有什麼是拼搏
假如沒有OI，我可能會和同學們一樣，週末去網吧聯機dota
假如沒有OI，我以後可能永遠也接觸不到演算法和編程
假如沒有OI，我會像所有的普通人一樣，平平淡淡，終其一生

各種字符串Hash函數比較

本文轉載自：http://www.byvoid.com/blog/string-hash-compare/
轉載請註明出處。

常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。
常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。

Hash函数	数据1	数据2	数据3	数据4	数据1得分	数据2得分	数据3得分	数据4得分	平均分
BKDRHash	2	0	4774	481	96.55	100	90.95	82.05	92.64
APHash	2	3	4754	493	96.55	88.46	100	51.28	86.28
DJBHash	2	2	4975	474	96.55	92.31	0	100	83.43
JSHash	1	4	4761	506	100	84.62	96.83	17.95	81.94
RSHash	1	0	4861	505	100	100	51.58	20.51	75.96
SDBMHash	3	2	4849	504	93.1	92.31	57.01	23.08	72.41
PJWHash	30	26	4878	513	0	0	43.89	0	21.95
ELFHash	30	26	4878	513	0	0	43.89	0	21.95

其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与 1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。
经过比较，得出以上平均得分。平均数为平方平均数。可以发现，BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也 是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算 法本质是相似的。
在信息修竞赛中，要本着易于编码调试的原则，个人认为BKDRHash是最适合记忆和使用的。
BYVoid原创，欢迎建议、交流、批评和指正。
附：各种哈希函数的C语言程序代码

unsigned int SDBMHash(char *str)
{
 unsigned int hash = 0;
 
 while (*str)
 {
  // equivalent to: hash = 65599*hash + (*str++);
  hash = (*str++) + (hash << 6) + (hash << 16) - hash;
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// RS Hash Function
unsigned int RSHash(char *str)
{
 unsigned int b = 378551;
 unsigned int a = 63689;
 unsigned int hash = 0;
 
 while (*str)
 {
  hash = hash * a + (*str++);
  a *= b;
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// JS Hash Function
unsigned int JSHash(char *str)
{
 unsigned int hash = 1315423911;
 
 while (*str)
 {
  hash ^= ((hash << 5) + (*str++) + (hash >> 2));
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
 unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
 unsigned int ThreeQuarters = (unsigned int)((BitsInUnignedInt  * 3) / 4);
 unsigned int OneEighth  = (unsigned int)(BitsInUnignedInt / 8);
 unsigned int HighBits   = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
 unsigned int hash    = 0;
 unsigned int test    = 0;
 
 while (*str)
 {
  hash = (hash << OneEighth) + (*str++);
  if ((test = hash & HighBits) != 0)
  {
   hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
  }
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// ELF Hash Function
unsigned int ELFHash(char *str)
{
 unsigned int hash = 0;
 unsigned int x = 0;
 
 while (*str)
 {
  hash = (hash << 4) + (*str++);
  if ((x = hash & 0xF0000000L) != 0)
  {
   hash ^= (x >> 24);
   hash &= ~x;
  }
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
 unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
 unsigned int hash = 0;
 
 while (*str)
 {
  hash = hash * seed + (*str++);
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// DJB Hash Function
unsigned int DJBHash(char *str)
{
 unsigned int hash = 5381;
 
 while (*str)
 {
  hash += (hash << 5) + (*str++);
 }
 
 return (hash & 0x7FFFFFFF);
}
 
// AP Hash Function
unsigned int APHash(char *str)
{
 unsigned int hash = 0;
 int i;
 
 for (i=0; *str; i++)
 {
  if ((i & 1) == 0)
  {
   hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
  }
  else
  {
   hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
  }
 }
 
 return (hash & 0x7FFFFFFF);
}