over 3 years ago

floyd没学好,本应该想出来的,应该想的再深入一点
卡住的地方应该是:可以轻松统计出最短路数目,但是对于经过一个点的最短路开始觉得没办法统计,因为经过k点的话对点会有k的限制
事实是:如果第一遍已经统计出了所有最短路径条数,那么就会包含超过k的点
tricky:
1、不能复制为正无穷,会加爆
2、unsigned爆掉会变成0

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int map[101][101]={0};
long long sum[101][101]={0};
int n,m;
double ans[101]={0};
int read()
{
    int bj=1,result=0;char c=getchar();
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') bj=-1,c=getchar();
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return bj*result;
}
int main()
{   int i,j,k,x,y,z;
    memset(map,0x3f,sizeof(map));
    n=read();m=read();
    for (i=1;i<=m;i++)
    {
        x=read();y=read();z=read();
        map[x][y]=map[y][x]=z;
        sum[x][y]=sum[y][x]=1;
    }
    for (k=1;k<=n;k++)
     for (i=1;i<=n;i++)
     if (i!=k)
      for (j=1;j<=n;j++)
        if (j!=k&&j!=i)
            if (map[i][k]+map[k][j]<map[i][j])
            {
                map[i][j]=map[i][k]+map[k][j];
                sum[i][j]=sum[i][k]*sum[k][j];
            }
            else
            if (map[i][k]+map[k][j]==map[i][j])
                sum[i][j]+=sum[i][k]*sum[k][j];
    for (k=1;k<=n;k++)
    {
     for (i=1;i<=n;i++)
     if (i!=k)
      for (j=1;j<=n;j++)
        if (j!=k&&j!=i)
        if (map[i][k]+map[k][j]==map[i][j])
          ans[k]+=(sum[i][k]*sum[k][j])/(double)sum[i][j];
     printf("%.3lf\n",ans[k]);
    }
}
← 【bzoj1225】求正整数 【poj1639】【度限制最小生成树】Picnic Planning →
 
comments powered by Disqus