A.绿豆蛙的归宿
\(f[x]\) 表示从x走到终点经过的路径的期望长度。
从 \(x\) 出发经过 \(k\) 条边，则有：
由于\(f[N]=0\)，所以从终点出发在反图上跑拓扑排序。
点击查看代码
#include <bits/stdc++.h>
#define kw 0
using namespace std;
const int N=200010;
int to[N],edge[N],nxt[N],head[N],in[N],out[N];
int n,m,x,y,z,tot;
double dis[N];
queue<int> q;
void add(int x,int y,int z){
to[++tot]=y;
edge[tot]=z;
nxt[tot]=head[x];
head[x]=tot;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
add(y,x,z);
in[x]++;
out[x]++;
}
q.push(n);
while(q.size()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
dis[y]+=(dis[x]+edge[i])/in[y];
out[y]--;
if(!out[y]) q.push(y);
}
}
printf("%.2f\n",dis[1]);
return kw;
}
B.
聪聪和可可
这个题吧还是不太好分析整个过程的，比较麻烦
大概意思就是猫进行一系列神奇走位靠近鼠