本文共 2086 字，大约阅读时间需要 6 分钟。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define MOD 1000000007 10 const int INF=0x3f3f3f3f; 11 const double eps=1e-5; 12 typedef long long ll; 13 #define cl(a) memset(a,0,sizeof(a)) 14 #define ts printf("*****\n"); 15 int n,m,tt; 16 const int MAXN = 1010; 17 const int MAXM = 1010*4; 18 int mp[MAXN][MAXN]; 19 struct Edge 20 { 21 int to,next; 22 }edge[MAXM]; 23 int head[MAXN],tot; 24 void addedge(int u,int v) 25 { 26 edge[tot].to = v; 27 edge[tot].next = head[u]; 28 head[u] = tot++; 29 30 } 31 32 void init() 33 { 34 tot = 0; 35 memset(head,-1,sizeof(head)); 36 } 37 38 void bfs(int st) 39 { 40 queue q; 41 q.push(st); 42 mp[st][st]=0; 43 while(!q.empty()) 44 { 45 int u=q.front(); 46 q.pop(); 47 for(int i=head[u];i!=-1;i=edge[i].next) 48 { 49 int v=edge[i].to; 50 if(v==u) continue; 51 if(mp[st][v]==-1) 52 { 53 mp[st][v]=mp[st][u]+1; 54 q.push(v); 55 } 56 } 57 } 58 } 59 int to[MAXN][MAXN]; 60 double f[MAXN][MAXN]; 61 bool vis[MAXN][MAXN]; 62 double F(int x,int y) 63 { 64 if(vis[x][y]) return f[x][y]; 65 vis[x][y]=1; 66 if(mp[x][y]==0) return f[x][y]=0.0; 67 if(mp[x][y]<=2) return f[x][y]=1.0; 68 double val=0; 69 int cnt=0; 70 int v; 71 for(int i=head[y];i!=-1;i=edge[i].next) 72 { 73 cnt++; 74 v=edge[i].to; 75 val+=F(to[to[x][y]][y],v); 76 } 77 return f[x][y]=val/cnt+1.0; 78 } 79 void fun() 80 { 81 for(int i=1;i<=n;i++) 82 { 83 for(int j=1;j<=n;j++) 84 { 85 printf("%.2lf ",f[i][j]); 86 } 87 printf("\n"); 88 } 89 } 90 int main() 91 { 92 int s,t; 93 int i,j,k; 94 #ifndef ONLINE_JUDGE 95 freopen("1.in","r",stdin); 96 #endif 97 init(); 98 scanf("%d%d%d%d",&n,&m,&s,&t); 99 int u,v;100 for(i=0;i mp[k][v])119 {120 mx=mp[k][v];121 to[j][k]=v;122 }123 else if(mx==mp[k][v])124 {125 to[j][k]=min(v,to[j][k]);126 }127 }128 }129 }130 for(i=1;i<=n;i++)131 {132 addedge(i,i);133 }134 printf("%.3lf\n",F(s,t));135 return 0;136 }
转载于:https://www.cnblogs.com/cnblogs321114287/p/4788978.html
