题解 P2047 【社交网络】

· · 题解

分析：说白了，这题唯一比较有挑战性的地方，就是求任意两点间最短路的条数。

这里说一个很没有节操的方法：

floyd 都会吧，好，那接着说，不会的 google 。

转移的时候增加一下路径的转移：

　　　　if a[i,k]+a[k,j]<a[i,j] then 
　　　　　　a[i,j]:=......
　　　　　　f[i,j]:=f[i,k]*f[k,j];               //f 是最短路径的条数，这个的来源是乘法原理。
　　　　else
　　        if a[i,k]+a[k,j]=a[i,j] then f[i,j]:=f[i,j]+a[i,k]*a[k,j];   //这个是加法原理。

然后，枚举每两个点，直接计算重要程度就可以了。。。。。

代码：SueMiller


var 
    a:array[0..101,0..101]of longint;
    f:array[0..101,0..101]of int64;
    v:array[0..101]of double;
    n,m,x,y,z,i,j,k:longint;
begin
    readln(n,m);
    filldword(a,sizeof(a)>>2,maxlongint>>2);
    fillchar(v,sizeof(v),0);
    for i:=1 to m do begin
        readln(x,y,z);
        a[x,y]:=z;
        a[y,x]:=z;
        f[x,y]:=1;
        f[y,x]:=1;
    end;
    for k:=1 to n do
        for i:=1 to n do
            if i<>k then
                for j:=1 to n do
                    if (i<>k) and (j<>k) then
                        if a[i,k]+a[k,j]<a[i,j] then begin
                            a[i,j]:=a[i,k]+a[k,j];
                            f[i,j]:=f[i,k]*f[k,j];
                        end
                        else if a[i,k]+a[k,j]=a[i,j] then
                            f[i,j]:=f[i,j]+f[i,k]*f[k,j];
    for k:=1 to n do begin
        for i:=1 to n do
            if i<>k then
                for j:=1 to n do
                    if (i<>j) and (k<>j) then begin
                        if (a[i,k]+a[k,j]<>a[i,j]) then continue;
                        if f[i,j]=0 then continue;
                        v[k]:=v[k]+(f[i,k]*f[k,j])/f[i,j];
                    end;
        writeln(v[k]:0:3);
    end;
end.