[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 }

 

 

 

 

上一篇:P2973 [USACO10HOL]赶小猪


下一篇:python基于词向量的古诗生成器