蓝桥杯 观光铁路
原题链接并没有解题思路源代码
原题链接
历年真题 观光铁路
并没有解题思路
这道题我一开始想对于每个点进行一次DFS，在到达边界时（再次回到该点）：累计每条路径经过的边数，路径条数加1。然后该点的期望时间就是总边数/路径条数。
但是做的时候发现我无法保证不会回头，因为是无向边，可能1->2，然后2->1，一直死循环下去回不到起点。本来1->2，那可以通过将该边删去，防止回头，但是因为其他点的路径可能需要这条边，所以不能删去，因此没有想到更好的办法处理。
然后在网上只看到了SPFA算法运用于非最短路问题的解释，并不是很好理解。
后来观察样例发现用每个点的期望时间刚好是：所有点的度数之和/每个点的度数，这样写竟然有65分，不知道是巧合还是的确可以这样统计，期待更好的解答。
源代码
#include<iostream>
#include<vector>
using namespace std
;
const int maxn
= 25;
int n
, m
;
vector
<int> child
[maxn
];
long long total(){
long long sum
= 0;
for(int i
=1; i
<=n
; i
++){
sum
+= child
[i
].size();
}
return sum
;
}
int degree(int x
){
return child
[x
].size();
}
int main(){
scanf("%d%d", &n
, &m
);
int u
, v
;
for(int i
=0; i
<m
; i
++){
scanf("%d%d", &u
, &v
);
child
[u
].push_back(v
);
child
[v
].push_back(u
);
}
long long sum
= total();
double res
;
for(int i
=1; i
<=n
; i
++){
res
= (1.0*sum
)/degree(i
);
printf("%.12f\n", res
);
}
return 0;
}
