[BZOJ1491]社交网络
知识点：Floyd+初赛数学水平
难点：最短路计数？
分析： n<=100，每个点都要输出，又和最短路有关
“红(chi)果(luo)果(luo)”的告诉你要Floyd啊
最短路显然不要说了，看看如何计数：
过两个点的最短路条数：
\begin{matrix} \sum_{k,dis[i][k]+dis[k][j]<dis[i][j]} cnt[i][k]*cnt[k][j] \end{matrix}
然后一直更新就好了，看公式难理解的话直接看代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #define int long long 6 using namespace std; 7 inline int read(){ 8 char chr=getchar(); int f=1,ans=0; 9 while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();} 10 while(isdigit(chr)) {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();} 11 return ans*f; 12 }int n,m,dis[105][105],cnt[105][105]; 13 double ANS[105]; 14 #define F for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) 15 signed main(){memset(dis,0x3f,sizeof(dis)),memset(cnt,0,sizeof(cnt)); 16 n=read(),m=read(); 17 for(int i=1,x,y;i<=m;i++)x=read(),y=read(),dis[x][y]=dis[y][x]=read(),cnt[x][y]=cnt[y][x]=1; 18 F{ 19 if(dis[i][j]==dis[i][k]+dis[k][j]) 20 cnt[i][j]+=cnt[i][k]*cnt[k][j]; 21 if(dis[i][j]>dis[i][k]+dis[k][j]) 22 cnt[i][j]=cnt[i][k]*cnt[k][j],dis[i][j]=dis[i][k]+dis[k][j]; 23 }F 24 if(i!=j&&i!=k&&k!=j&&dis[i][j]==dis[i][k]+dis[k][j]) 25 ANS[k]+=(1.0*cnt[i][k]*cnt[k][j])/cnt[i][j]; 26 for(int i=1;i<=n;i++) printf("%0.3lf\n",(ANS[i])); 27 return 0; 28 }
投递三维家等公司10个岗位