BZOJ 1491 [NOI2007] 社交网络


题目链接: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]....

代码如下:

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1491 [NOI2007] 社交网络


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,