首页 > 代码库 > 1491: [NOI2007]社交网络
1491: [NOI2007]社交网络
1491: [NOI2007]社交网络
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 881 Solved: 518
[Submit][Status]
Description
Input
Output
输出文件包括n 行，每行一个实数，精确到小数点后3 位。第i 行的实数表 示结点i 在社交网络中的重要程度。
Sample Input
4 4
1 2 1
2 3 1
3 4 1
4 1 1
1 2 1
2 3 1
3 4 1
4 1 1
Sample Output
1.000
1.000
1.000
1.000
1.000
1.000
1.000
HINT
为1
Source
题解：这个嘛，我还是小小地逗比了一下（phile：汗 HansBug：T_T）——题目中说每次求出来的是s到t最短路径中经过v点的路径所占的比例，但是我还是当作占经过各点路径之和的比例了（phile：那不是重复计算了嘛 HansBug：么么哒）。。。然后说思路——其实这道题的思想有点类似于Bzoj1638（奶牛交通），通过求出各个部分的局部值来进行组合求解——在Floyd过程中，当a[i,j]=a[i,k]+a[k,j]时，则用于存储数量的b[i,j]:=b[i,j]+b[i,k]*b[k,j]（简单乘法原理），当a[i,j]>a[i,k]+a[k,j]（即最短路径长度被刷新时），则b[i,j]:=b[i,k]*b[k,j];然后这样字O(n^3)（N<=100呢怕啥）处理完，然后再来个O(n^3)负责统计即可。。。（HansBug：记得开int64/long long啊！！！题目中最短路径数是<=10^10，要是longint小心跪掉。。。）
1 var 2 i,j,k,l,m,n,s,t:longint; 3 a,b:array[0..150,0..150] of int64; 4 c:array[0..150] of int64; 5 d:array[0..150] of extended; 6 begin 7 readln(n,m); 8 fillchar(a,sizeof(a),0); 9 fillchar(b,sizeof(b),0);10 for i:=1 to n do b[i,i]:=1;11 for i:=1 to m do12 begin13 readln(j,k,l);14 a[j,k]:=l;a[k,j]:=l;15 b[j,k]:=1;b[k,j]:=1;16 end;17 for k:=1 to n do18 for i:=1 to n do19 begin20 if (i<>k) and (a[i,k]>0) then21 begin22 for j:=1 to n do23 begin24 if (i<>j) and (j<>k) and (a[k,j]>0) then25 begin26 if ((a[k,j]+a[i,k])=a[i,j]) then27 begin28 b[i,j]:=b[i,j]+(b[i,k]*b[k,j]);29 end30 else31 begin32 if ((a[k,j]+a[i,k])<a[i,j]) or (a[i,j]=0) then33 begin34 a[i,j]:=a[k,j]+a[i,k];35 b[i,j]:=b[i,k]*b[k,j];36 end;37 end;38 end;39 end;40 end;41 end;42 fillchar(d,sizeof(d),0);43 for s:=1 to n do44 for t:=1 to n do45 begin46 if s=t then continue;47 fillchar(c,sizeof(c),0);48 for i:=1 to n do49 begin50 if (s=i) or (t=i) then continue;51 if (a[s,i]+a[i,t])<>a[s,t] then continue;52 d[i]:=d[i]+(b[s,i]*b[i,t])/b[s,t];53 end;54 end;55 for i:=1 to n do writeln(d[i]:0:3);56 end.
1491: [NOI2007]社交网络
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。