建平县网站建设,安阳哪里做360网站,我要自学网免费视频教程,wordpress自动汉化正题
题面链接:https://www.luogu.com.cn/problem/P6030 题目大意 nnn个点的一张有向图#xff0c;求起点到终点的期望步数。保证每个强连通分量大小不超过100100100。 解题思路
显然如果是强连通分量那么显然需要用高斯消元。
先把强连通用tarjantarjantarjan缩起来#…正题
题面链接:https://www.luogu.com.cn/problem/P6030 题目大意
nnn个点的一张有向图求起点到终点的期望步数。保证每个强连通分量大小不超过100100100。 解题思路
显然如果是强连通分量那么显然需要用高斯消元。
先把强连通用tarjantarjantarjan缩起来如果有任何不是ttt的节点没有出度那么答案都为INFINFINF然后剩下的每个用高斯消元做一次即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includevector
#includecmath
#includestack
using namespace std;
const int N1e410;
int n,m,s,t,out[N],deg[N],top[N],pos[N];
int cnt,num,col[N],dfn[N],low[N];
double ans[N];bool ins[N];
vectorint v[N];
stackint st;
struct Graph{int ls[N],tot;struct node{int from,to,next;}a[N*200];void addl(int x,int y){a[tot].toy;a[tot].fromx;a[tot].nextls[x];ls[x]tot;return;}
}G,D;
struct Guass{double a[110][110],b[110];void solve(int n){for(int i1;in;i){int zi;for(int ji1;jn;j)if(fabs(a[j][i])fabs(a[z][i]))zj;for(int j1;jn;j)swap(a[i][j],a[z][j]);swap(b[z],b[i]);for(int j1;jn;j){if(ij)continue;double ratea[j][i]/a[i][i];for(int ki;kn;k)a[j][k]-rate*a[i][k];b[j]-rate*b[i];}}for(int i1;in;i)b[i]/a[i][i];return;}
}M;
void tarjan(int x){dfn[x]low[x]cnt;st.push(x);ins[x]1;for(int iG.ls[x];i;iG.a[i].next){int yG.a[i].to;if(!dfn[y]){tarjan(y);low[x]min(low[x],low[y]); }else if(ins[y])low[x]min(low[x],dfn[y]);}if(dfn[x]low[x]){num;while(st.top()!x){col[st.top()]num;v[num].push_back(st.top());ins[st.top()]0;st.pop();}col[st.top()]num;v[num].push_back(st.top());ins[st.top()]0;st.pop();}return;
}
void topsort(){int head1,tail1;top[1]col[s];while(headtail){int xtop[head];for(int iD.ls[x];i;iD.a[i].next){int yD.a[i].to;deg[y]--;if(!deg[y])top[tail]y;}}return;
}
void calc(int id){int cnt0;for(int i0;iv[id].size();i)pos[v[id][i]]cnt;memset(M.a,0,sizeof(M.a));memset(M.b,0,sizeof(M.b));for(int p0;pv[id].size();p){int xv[id][p];if(!out[x])return;for(int iG.ls[x];i;iG.a[i].next){int yG.a[i].to;if(col[x]!col[y])M.b[pos[x]]1.0*ans[y]/out[x];else M.a[pos[x]][pos[y]]-1.0/out[x];}M.a[pos[x]][pos[x]]1;M.b[pos[x]]1;}M.solve(cnt);for(int i0;iv[id].size();i)ans[v[id][i]]M.b[i1];return;
}
int main()
{scanf(%d%d%d%d,n,m,s,t);for(int i1;im;i){int x,y;scanf(%d%d,x,y);if(x!t){out[x];G.addl(x,y);}}tarjan(s);for(int i1;iG.tot;i){int xG.a[i].from,yG.a[i].to;if(col[x]!col[y]col[x]!col[t])deg[col[x]];}for(int i1;in;i){if(it!dfn[i])return printf(INF\n)0;if(col[i]!col[t]dfn[i]!deg[col[i]])return printf(INF\n)0;}memset(deg,0,sizeof(deg));for(int i1;iG.tot;i){int xG.a[i].from,yG.a[i].to;if(!col[x]||!col[y]||col[x]col[t])continue;if(col[x]!col[y]){D.addl(col[x],col[y]);deg[col[y]];}}topsort();for(int inum;i1;i--)calc(top[i]);printf(%.3lf,ans[s]);
}
