NOI2007 社交網絡 network 解題報告

【題目描述】 
 懶得貼上試題了～發個連結：NOI2007 Day1試題連結
 【分析】
這是這幾年NOI中最簡單的題了～就是一個多源最短路+乘法原理。 

用Map[i][j]表示i、j之間的最短路徑長度； 
用Path[i][j]表示i、j之間最短路徑的條數（初始化為1）。

 先用Floyd算法求每兩點之間的最短路，鬆弛時要注意，如果出現：
 Map[i][k]+Map[k][j]==Map[i][j] 則說明這又是最短路，所以Path[i][j]+=Path[i][k]*Path[k][j]。
 如果可以鬆弛，即Map[i][k]+Map[k][j]<Map[i][j]，則Path[i][j]=Path[i][k]*Path[k][j]即可。

 最後亂搞一個三重循環求I(v)，按照題意走即可AC。



 【我的代碼】
裸代碼RawCode

1. #include <cstdio>
2. #include <cstdlib>
3. #define inputfile freopen("network.in","r",stdin)
4. #define outputfile freopen("network.out","w",stdout)
5. #define MAXN 101
6. #define MAX 1000000000
7. #define LL long long
9. using namespace std;
10. int N,M;
11. int Map[MAXN][MAXN];
12. LL Path[MAXN][MAXN];
14. void init()
15. {
16.     fscanf(stdin,"%d %d\n",&N,&M);
17.     for(int i=1;i<=N;i++)
18.     {
19.         for(int j=1;j<=N;j++)
20.             Map[i][j]=MAX,Path[i][j]=1;
21.         Map[i][i]=0;
22.     }
23.    
24.     int a,b,v;
25.     for (int i=1;i<=M;i++)
26.     {
27.         fscanf(stdin,"%d %d %d\n",&a,&b,&v);
28.         Map[a][b]=v;
29.         Map[b][a]=v;
30.     }
31. }
33. void Floyd()
34. {
35.     for (int k=1;k<=N;k++)
36.     {
37.         for (int i=1;i<=N;i++)
38.         {
39.             for (int j=1;j<=N;j++)
40.             {
41.                 if(k==i || k==j || i==j)
42.                         continue;
43.                 if(Map[i][k]+Map[k][j]==Map[i][j])
44.                     Path[i][j]+=Path[i][k]*Path[k][j];
45.                 if(Map[i][k]+Map[k][j]<Map[i][j])
46.                     Map[i][j]=Map[i][k]+Map[k][j],
47.                     Path[i][j]=Path[i][k]*Path[k][j];
48.             }
49.         }
50.     }
51. }
53. void solve()
54. {
55.     for (int v=1;v<=N;v++)
56.     {
57.         double Ans=0;
58.         for (int s=1;s<=N;s++)
59.         {
60.             for (int t=1;t<=N;t++)
61.             {
62.                 if(s==v || t==v || s==t)
63.                     continue;
64.                 if(Map[s][v]+Map[v][t]!=Map[s][t])
65.                     continue;
66.                 double a=double(Path[s][v]*Path[v][t]);
67.                 double b=double(Path[s][t]);
68.                 double res=a/b;
69.                 Ans+=res;
70.             }
71.         }
72.         fprintf(stdout,"%.3lf\n",Ans);
73.     }
74. }
76. int main()
77. {
78.     inputfile,outputfile;
79.     init();
80.     Floyd();
81.     solve();
82.     return 0;
83. }