BZOJ 1491 [NOI2007] 社交网络

发布于 2017-04-25  120 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1491

题意:一个无向图,某个节点 i 的重要程度定义为所有点对 s,t 不同的最短路数量比通过 i 的最短路数量的和... 求所有点的重要程度... 具体式子可以看原题


为了写 floyd 的算法详解去刷一刷水题.... 结果还是 wa 了一发... 原来 double 赋值 inf 不能用 memset...

我们用 w[i][j] 表示从 i 到 j 不同的最短路数量... 那么很明显,ans[k]=(w[i][k]*w[k][j])/w[i][j]

考虑怎么求得 w[i][j],正常走 floyd,若更新两点间最短路,则旧 w[i][j] 无意义,我们重新赋值 w[i][j]=w[i][k]*w[k][j],这么做是显然的...

若更新时发现两种情况 dis 相等,则发现了一条新的最短路,累加答案 w[i][j]+=w[i][k]*w[k][j]....

代码如下:

 


一个非常弱的准退役OIER