题解 P2047 【[NOI2007]社交网络】

## 来一个SPFA的题解 ## 先上代码 ``` #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #define ll long long using namespace std; int read() { char ch=getchar();int h=0,t=1; while((ch>'9'||ch<'0')&&ch!='-') ch=getchar(); if(ch=='-') t=-1,ch=getchar(); while(ch>='0'&&ch<='9') h=h*10+ch-'0',ch=getchar(); return h*t; } int N,M,g[110][110],head[110],cnt; int dis[110],vis[110]; ll w[110][110],fr[110][110][110]; queue<int>Q; struct edge{int next,to,w;}a[10010]; void link(int x,int y,int w){a[++cnt]=(edge){head[x],y,w};head[x]=cnt;} void SPFA(int f) { memset(dis,63,sizeof(dis)); Q.push(f);vis[f]=1;dis[f]=0;w[f][f]=1; while(!Q.empty()) { int x=Q.front(); for(int i=head[x];i;i=a[i].next) { int R=a[i].to; if(dis[R]<dis[x]+a[i].w) continue; if(dis[R]==dis[x]+a[i].w) { w[f][R]=w[f][R]-fr[f][R][x]+w[f][x]; fr[f][R][x]=w[f][x]; } else { dis[R]=dis[x]+a[i].w; w[f][R]=w[f][x]; for(int p=1;p<=N;p++) fr[f][R][p]=0; fr[f][R][x]=w[f][x]; } if(!vis[R]) vis[R]=1,Q.push(R); } Q.pop();vis[x]=0; } for(int i=1;i<=N;i++) g[f][i]=dis[i]; } int main() { N=read();M=read(); for(int i=1;i<=M;i++) { int x=read(),y=read(),w=read(); link(x,y,w);link(y,x,w); } for(int i=1;i<=N;i++) SPFA(i); for(int k=1;k<=N;k++) { double ans=0; for(int x=1;x<=N;x++) for(int y=1;y<=N;y++) if(x!=k&&k!=y&&g[x][y]==g[x][k]+g[k][y]) ans+=1.0*w[x][k]*w[k][y]/w[x][y]; printf("%.3lf\n",ans); } return 0; } ``` 这题由于ans+=w[x][k]*w[k][y]/x[x][y]，没有乘w[k][y]而调试半个小时，甚至还尝试了Floyd的做法 意思就是x->y，那么w(ay)[y]+=w(ay)[x]，但是x被松弛后不能直接加，就要用fr来记录x对y的路径条数的贡献 Floyd相对好写些，这里只提供一个SPFA的思路，Floyd可以看楼下的，写的很棒