题解 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可以看楼下的，写的很棒