题目描述
求图中每一个点在所有点对的最短路中被覆盖的比例。
样例
4 4
1 2 1
2 3 1
3 4 1
4 1 1
1.000
1.000
1.000
1.000
算法1
(暴力枚举(Floyed)) $O(n^3)$
看到这题,想了想,好像只想出Floyed暴力写法。(然而数据就$N \le 100$,可以接受)
先$O(n^3)$跑出任意两点的最短距离和路径总数,再枚举每一个点,枚举点对,看那一对点对的最短路是经过这个点的,累计即可。
if(d[i][u]+d[u][j]==d[i][j])//如果强制经过点u后(i,j)最短路距离不变,则可统计答案
ans+=cnt[i][u]*cnt[u][j];//不直接使用cnt[i][j]是因为可能还有其他方法跑最短
时间复杂度
显然$O(n^3)$
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
int d[110][110];
long long cnt[110][110];
int main(){
int n,m,a,b,c;
cin>>n>>m;
for(int i=0;i<=n;i++)//初始化
for(int j=0;j<=n;j++)
d[i][j]=1000000000;
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
d[a][b]=d[b][a]=c;
cnt[a][b]=cnt[b][a]=1;
}
for(int k=1;k<=n;k++)//Floyed跑任意两点最短路并计数
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j&&j!=k&&k!=i){
if(d[i][k]+d[k][j]==d[i][j])
cnt[i][j]+=cnt[i][k]*cnt[k][j];//乘法原理
else
if(d[i][k]+d[k][j]<d[i][j]){
d[i][j]=d[i][k]+d[k][j];
cnt[i][j]=cnt[i][k]*cnt[k][j];
}
}
for(int u=1;u<=n;u++){//枚举点
double ans2=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j&&j!=u&&u!=i&&cnt[i][j])
if(d[i][u]+d[u][j]==d[i][j])//如果最短路经过它
ans2+=cnt[i][u]*cnt[u][j]*1.0/cnt[i][j];
printf("%0.3lf\n",ans2);
}
return 0;
}
要是有重边,怎么办
题目说了, 两个节点最多一条边