P3232 [HNOI2013]游走
题目描述
一个无向连通图，顶点从\(1\)编号到\(N\)，边从\(1\)编号到\(M\)。 小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z 到达\(N\)号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小。
输入输出格式
输入格式：
第一行是正整数\(N\)和\(M\)，分别表示该图的顶点数和边数，接下来\(M\)行每行是整数\(u,v(1\le u,v\le N)\)，表示顶点\(u\)与顶点\(v\)之间存在一条边。
输入保证\(30\%\)的数据满足\(N\le 10\)，\(100\%\)的数据满足\(2\le N\le 500\)且是一个无向简单连通图。
输出格式：
仅包含一个实数，表示最小的期望值，保留3位小数。
\(f_i\)代表\(i\)这个点的期望经过次数，\(d_i\)表示度数
\[ f_v=\sum \frac{f_u}{d_u} \] 1号点的方程常数加1，代表它原来就有1的次数，n号点不被转移走然后求每条边的期望经过次数
\[ E_{u,v}=\frac{f_u}{d_u}+\frac{f_v}{d_v} \] 然后对边的期望次数排序，贪心匹配即可。Code:
#include#include #include const int N=520;int head[N],to[N*N],Next[N*N],cnt;void add(int u,int v){ to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;}int n,m,eu[N*N],ev[N*N],in[N];double a[N][N],ct[N*N];void Gauss(){ for(int i=1;i<=n;i++) { int id=i; for(int j=i+1;j<=n;j++) if(fabs(a[j][i])>fabs(a[id][i])) id=j; std::swap(a[id],a[i]); for(int j=n+1;j>=i;j--) a[i][j]/=a[i][i]; for(int j=i+1;j<=n;j++) for(int k=n+1;k>=i;k--) a[j][k]-=a[i][k]*a[j][i]; } for(int i=n;i;i--) for(int j=i-1;j;j--) a[j][n+1]-=a[i][n+1]*a[j][i];}int main(){ scanf("%d%d",&n,&m); for(int u,v,i=1;i<=m;i++) { scanf("%d%d",&u,&v); add(u,v),add(v,u); ++in[u],++in[v]; eu[i]=u,ev[i]=v; } a[1][n+1]=1; for(int u=1;u<=n;u++) { a[u][u]=1; for(int i=head[u];i;i=Next[i]) if(to[i]!=n) a[u][to[i]]=-1.0/in[to[i]]; } Gauss(); for(int i=1;i<=m;i++) { if(eu[i]!=n) ct[i]=a[eu[i]][n+1]/in[eu[i]]; if(ev[i]!=n) ct[i]+=a[ev[i]][n+1]/in[ev[i]]; } std::sort(ct+1,ct+1+m); double ans=0; for(int i=1;i<=m;i++) ans+=ct[i]*(m+1-i); printf("%.3f\n",ans); return 0;}
2019.1.12