求經過邊的期望次數，然后邊的編號相當于給期望一個系數，期望大到小給編號就好

假如可以強行改邊為點高斯消元的話是很方便的，然而并不資瓷

但是我們可以先把經過點的期望次數求出來：f(u)=sigema((u,v)屬于E且v!=n)v f(v)/du(v)，特別的，f(1)在右邊還要加上一個1

對于1條邊而言，走過它的期望次數就是它兩端的點相互給對方的貢獻

所以g(k)=f(u)/du(u)（當u!=n時）+f(u)/du(u)（當v!=n時）

#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std;struct node {int x,y,next; }a[510000];int len,last[510];int du[510]; void ins(int x,int y) {len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len; }int n; double qg[510][510],qc[510]; void gauss() {for(int j=1;j<=n;j++){for(int i=j;i<=n;i++)if(fabs(qg[i][j])>1e-8){for(int k=1;k<=n;k++)swap(qg[i][k],qg[j][k]);swap(qc[i],qc[j]);break;}for(int i=1;i<=n;i++){if(i==j)continue;double rate=qg[i][j]/qg[j][j];for(int k=1;k<=n;k++)qg[i][k]-=qg[j][k]*rate;qc[i]-=qc[j]*rate;}} }int glen; double f[510],g[310000]; int main() {int m,x,y;scanf("%d%d",&n,&m);len=0;memset(last,0,sizeof(last));memset(du,0,sizeof(du));for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);ins(x,y),ins(y,x);du[x]++,du[y]++;}memset(qc,0,sizeof(qc));qc[1]=-1;for(x=1;x<=n;x++){qg[x][x]=-1;for(int k=last[x];k;k=a[k].next){y=a[k].y;if(y!=n)qg[x][y]=1.0/(double)du[y];}}gauss();for(int i=1;i<=n;i++)f[i]=qc[i]/qg[i][i];glen=0;for(int k=1;k<=len;k+=2){x=a[k].x,y=a[k].y;g[++glen]=0;if(x!=n)g[glen]+=f[x]/(double)du[x];if(y!=n)g[glen]+=f[y]/(double)du[y];}sort(g+1,g+glen+1);double ans=0;for(int i=1;i<=glen;i++)ans+=g[i]*(double)(glen-i+1);printf("%.3lf\n",ans);return 0; }

?

?

?

?

轉載于:https://www.cnblogs.com/AKCqhzdy/p/9882176.html

總結

以上是生活随笔為你收集整理的bzoj3143: [Hnoi2013]游走的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。