题157.2021秋周练习-2-3 社交网络图中结点的“重要性”计算 (25 分)

题157.2021秋周练习-2-3 社交网络图中结点的“重要性”计算(Floyd/bfs) (25 分)

一、题目

二、题解

本题要你求其余点到给定源点的距离总和的平均值的倒数，主要问题在于如何求其余点到给定源点的距离。方法一是直接用Floyd求多源最短路径，后面直接对源点到其余点距离求和就好。方法二是由于是无权图，所以问一次就使用一次bfs求单源最短路径，bfs结束距离之和就求出来了。虽然这里表面看都用了三层循环，但是用bfs的法子在最后一个测试点会快很多，因为这里bfs有一层循环是由K决定的，而K最大才100，然而Floyd循环都是N决定的，N最大直接10的四次方了。

//Floyd多源最短路径
#include <bits/stdc++.h>using namespace std;const int Inf=100100;int N,M;
int G[10010][10010];void init()//原本想用fill初始化的，但是那样会内存超限！！！
{for(int i=1;i<=N;i++){for(int j=1;j<=N;j++){if(i==j)//自己到自己初始化为0{G[i][j]=0;}else{G[i][j]=Inf;G[j][i]=Inf;}}}
}void Floyd()//Floyd求多源最短路径
{for(int k=1; k<=N; k++){for(int i=1; i<=N; i++){for(int j=1; j<=N; j++){if(G[i][k]<Inf&&G[k][j]<Inf&&G[i][j]>G[i][k]+G[k][j])//为了防止相加时数据溢出，所以在加之前的判断前加了个前提--中介边得连通{G[i][j]=G[i][k]+G[k][j];G[j][i]=G[j][k]+G[k][i];}}}}
}int main()
{cin>>N>>M;init();//一定要在N输入之后再初始化呀！！！for(int i=0; i<M; i++){int v1,v2;scanf("%d%d",&v1,&v2);G[v1][v2]=1;G[v2][v1]=1;}Floyd();int K;cin>>K;int flag=1;for(int i=0; i<K; i++){int s;scanf("%d",&s);int distsum=0;if(flag){for(int v=1; v<=N; v++){distsum+=G[s][v];}if(distsum>=Inf){printf("Cc(%d)=0.00\n",s);flag=0;}else{printf("Cc(%d)=%.2f\n",s,(N-1)/(float)distsum);}}else{printf("Cc(%d)=0.00\n",s);}}
}

//bfs单源最短路径
#include <bits/stdc++.h>using namespace std;int N,M;
int G[10010][10010];
int dist[10010];//记录下标表示的节点到源点的距离
int distsum;int bfs(int s)//直接bfs找无权图单源最短路径
{fill(dist,dist+10010,-1);//dist初始化为-1，表示未被访问过，没有距离int count0=N;//用于判断是否用一次bfs遍历完所有的顶点从而判断是否图连通queue<int> q;int v,w;dist[s]=0;distsum+=dist[s];//更新总距离q.push(s);count0--;//遍历到一个顶点数目减1while(!q.empty()){v=q.front();q.pop();for(w=1;w<=N;w++){if(G[v][w]==1&&dist[w]==-1){dist[w]=dist[v]+1;//因为w是由v到的，所以s到w距离为s到v的距离加1distsum+=dist[w];//更新总距离q.push(w);count0--;//遍历到一个顶点数目减1}}}if(count0==0)//所有的顶点都遍历了{return 1;}else{return 0;}
}int main()
{cin>>N>>M;for(int i=0; i<M; i++){int v1,v2;scanf("%d%d",&v1,&v2);G[v1][v2]=1;G[v2][v1]=1;}int K;cin>>K;int flag=1;for(int i=0; i<K; i++){int s;scanf("%d",&s);distsum=0;if(flag==1){if(bfs(s)){printf("Cc(%d)=%.2f\n",s,(N-1)/(float)distsum);}else{printf("Cc(%d)=0.00\n",s);flag=0;}}else{printf("Cc(%d)=0.00\n",s);}}
}