BZOJ-1491-社交网络

题目链接：https://vjudge.net/problem/HYSBZ-1491

题目大意：中文题目，题意见题目

题目分析：由于数据量很小，可以考虑进行Floyd算法。

第一次进行Floyd算法，算出两点之间的最短路径，另外记录下这两点之间有多长条最短路走法。

第二场进行类似Floyd算法的方法，计算经过k点，是否可以走出最短路，如果可以的话，进行计算。

注意在两次统计计算的过程中，要用组合的方法，即num[i][j]=num[i][k]*num[k][j];

给出代码：

 #include <iostream>
 #include <cstdio>
 #include <queue>
 #include <cstring>
 #include <string>
 using namespace std;

 int n,m;
 +][+];
 +][+];
 int inf=0x3f3f3f;
 ];
 int main()
 {
     cin>>n>>m;
     memset(node,inf,sizeof(node));
     //memset(node1,0,sizeof(node1));
     // memset(mark,0,sizeof(mark));
     ; i<m; i++)
     {
         int a,b,c;
         scanf("%d%d%d",&a,&b,&c);
         node[a][b]=c;
         node[b][a]=c;
         node1[a][b]=;
         node1[b][a]=;
     }
     // for(int i=1; i<=n; i++)
     //      node[i][i]=0;
   /*  for(int i=1; i<=n; i++)
     {
         for(int j=1; j<=n; j++)
         {
             cout<<node[i][j]<<" ";
         }
         cout<<endl;
     }
     cout<<endl;*/
     ; k<=n; k++)
     {
         ; i<=n; i++)
         {
             ; j<=n; j++)
             {
                 if(k!=i&&k!=j&&i!=j)
                 {
                     if(node[i][j]==node[i][k]+node[k][j])
                         node1[i][j]=node1[i][j]+(node1[i][k]*node1[k][j]);
                     else if(node[i][j]>node[i][k]+node[k][j])
                     {
                         node1[i][j]=node1[i][k]*node1[k][j];
                         node[i][j]=node[i][k]+node[k][j];
                     }
                 }
                // node[i][j]=
             }
         }
     }
    /* for(int i=1; i<=n; i++)
     {
         for(int j=1; j<=n; j++)
         {
             cout<<node[i][j]<<" ";
         }
         cout<<endl;
     }*/
     ; k<=n; k++)
     {
         ; i<=n; i++)
         {
             ; j<=n; j++)
             {

                 )
                 {
                     mark[k]+=((node1[i][k]*node1[k][j])/node1[i][j]);
                     // cout<<mark[k]<<" "<<k<<" "<<i<<" "<<j<<endl;
                  //   cout<<node1[i][k]<<" "<<node1[k][j]<<endl;
                 }
             }
         }
     }
     ; i<=n; i++)
         printf("%.3f\n",mark[i]);
     ;
 }

巴特西

BZOJ-1491-社交网络

最新文章

热门文章