先Tarjan缩点 强连通分量里用高斯消元外面直接转移 注意删掉终点出边和拓扑
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> #include<vector> #define N 10010 #define M 1000010 using namespace std; typedef double D; bool god=1; int n,m,s,e; struct Went { int to,next; }c[M],via[M],C[M]; int head[N],t,Head[N],T,adj[N],sz; inline void Add(int x,int y) { c[++t].to=y; c[t].next=head[x]; head[x]=t; C[++T].to=x; C[T].next=Head[y]; Head[y]=T; } inline void add(int x,int y) { via[++sz].to=y; via[sz].next=adj[x]; adj[x]=sz; } int dfn[N],low[N],num,sum[N],stack[N],top,belong[N],id[N]; D a[1200][1200],prob[N],exp[N],ans[1200]; int topo[N],out[N]; bool in[N],can_get[N]; vector<int> team[N]; int Time; inline int Min(int x,int y) { return x<y?x:y; } void tarjan(int x) { dfn[x]=low[x]=++Time; in[x]=1; stack[++top]=x; for(int i=head[x];i;i=c[i].next) if(!dfn[c[i].to]) { tarjan(c[i].to); low[x]=Min(low[x],low[c[i].to]); } else if(in[c[i].to]) low[x]=Min(low[x],dfn[c[i].to]); if(low[x]==dfn[x]) { int j; num++; do { j=stack[top--]; in[j]=0; sum[num]++; team[num].push_back(j); id[j]=team[num].size(); belong[j]=num; }while(j!=x); } } int bang[N]; void buildnew() { for(int x=1;x<=n;x++) { for(int i=head[x];i;i=c[i].next) { bang[x]++; int y=c[i].to; if(belong[x]==belong[y])continue; add(belong[x],belong[y]); } } } int tool; int indegree[N]; void light(int x) { can_get[x]=1; for(int i=adj[x];i;i=via[i].next) { out[x]++; indegree[via[i].to]++; if(!can_get[via[i].to]) light(via[i].to); } if(out[x]==0)tool++; } queue<int> q; int size; void bfs() { q.push(belong[s]); while(!q.empty()) { int x=q.front(); q.pop(); topo[++size]=x; for(int i=adj[x];i;i=via[i].next) { indegree[via[i].to]--; if(indegree[via[i].to]==0) q.push(via[i].to); } } } void dfs(int x) { printf(" Now : %d ",x); for(int i=adj[x];i;i=via[i].next) dfs(via[i].to); } void arrange() { buildnew(); light(belong[s]); if(can_get[belong[e]]==0)god=0; if(!god)return; if(out[belong[e]]!=0)god=0; if(!god)return; if(tool!=1)god=0; if(!god)return; bfs(); } void pre() { scanf("%d%d%d%d",&n,&m,&s,&e); if(s==e)return; for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); if(x==e)continue; Add(x,y); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); arrange(); if(!god)return; } inline D abs(D x) { return x<0.0?0.0-x:x; } inline void swap(D &x,D &y) { D z=x; x=y; y=z; } void gauss(int len) { for(int i=1,k=1;i<=len;i++,k++) { int temp=i; D host=abs(a[i][k]); for(int j=i+1;j<=len;j++) if(abs(a[j][k])>abs(a[temp][k])) { temp=j; host=abs(a[j][k]); } if(temp!=i) { for(int j=k;j<=len+1;j++) swap(a[i][j],a[temp][j]); } for(int j=i+1;j<=len;j++) { host=a[j][k]/a[i][k]; for(int l=k;l<=len+1;l++) a[j][l]-=a[i][l]*host; } } for(int i=len;i>0;i--) { for(int j=i+1;j<=len;j++) a[i][len+1]-=a[i][j]*ans[j]; ans[i]=a[i][len+1]/a[i][i]; } void work1() { prob[s]=1.0; for(int i=1;i<=size;i++) { int len=sum[topo[i]]; int x=topo[i]; for(int j=0;j<=len+1;j++) for(int k=0;k<=len+1;k++) a[j][k]=0.0; for(int j=0;j<len;j++) { int y=team[x][j]; a[j+1][len+1]-=prob[y]; a[j+1][j+1]+=-1.0; for(int k=Head[y];k;k=C[k].next) { int z=C[k].to; if(belong[z]!=x)continue; a[j+1][id[z]]+=1.0/bang[z]; } } gauss(len); for(int j=1;j<=len;j++) prob[team[x][j-1]]=ans[j]; for(int j=0;j<len;j++) { int y=team[x][j]; for(int k=head[y];k;k=c[k].next) { int z=c[k].to; if(belong[z]==x)continue; prob[z]+=1.0/bang[y]*prob[y]; } } } } void work2() { for(int i=1;i<=size;i++) { int len=sum[topo[i]]; int x=topo[i]; for(int j=0;j<=len+1;j++) for(int k=0;k<=len+1;k++) a[j][k]=0.0; for(int j=0;j<len;j++) { int y=team[x][j]; a[j+1][len+1]-=exp[y]; a[j+1][j+1]-=prob[y]; for(int k=Head[y];k;k=C[k].next) { int z=C[k].to; if(belong[z]!=x)continue; a[j+1][id[z]]+=prob[z]*1.0/bang[z]; a[j+1][len+1]-=prob[z]*1.0/bang[z]; } } gauss(len); for(int j=1;j<=len;j++) exp[team[x][j-1]]=ans[j]; for(int j=0;j<len;j++) { int y=team[x][j]; for(int k=head[y];k;k=c[k].next) { int z=c[k].to; if(belong[z]==x)continue; exp[z]+=(1.0/bang[y]*prob[y])*(exp[y]+1.0); } } } } void work() { work1(); work2(); } int main() { pre(); if(s==e) { printf("0.000"); return 0; } if(!god) { printf("INF"); return 0; } work(); printf("%.3lf",exp[e]); return 0; }