Vexoben
Jun 26, 2018
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=3143
（刷新以获取数学公式）
题意
一个无向连通图，顶点从编号到，边从编号到。
小Z在该图上进行随机游走，初始时小Z在号顶点，每一步小Z以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z到达号顶点时游走结束，总分为所有获得的分数之和。
现在，请你对这条边进行编号，使得小Z获得的总分的期望值最小。
题解
首先根据期望的线性性，我们知道总分的期望=所以边获得分数的期望和。
那么如果能求出每条边期望经过的次数，就可以贪心地给经过多的边标小序号。
设点的度数为，期望经过次，第条边连接和，期望经过次。那么我们得到：
现在问题转换为怎么求解。如果是DAG，显然可以用DP解决。对于一般图，我们可以列出方程：
就是说如果有的概率到点，那么如果存在边，就会对产生的贡献
有了上面的方程组，就可以利用高斯消元直接求解出。这也是计算互相影响的变量的常用方法。至此问题得以解决。
需要注意的是消元是要注意的情况。在实数下可能会有很大误差，需要调整。下面的代码在不能通过全部测试数据。
#include<bits/stdc++.h>
#define double long double
using namespace std;
const int N=505;
const double eps=1e-12;
int n,m;
int a[N][N],u[N*N],v[N*N],d[N];
double equ[N][N],x[N],p[N*N];
int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++) {
scanf("%d%d",&u[i],&v[i]);
d[u[i]]++; d[v[i]]++;
a[u[i]][v[i]]=a[v[i]][u[i]]=1;
}
for (int i=1;i<=n;i++) equ[i][i]=1;
for (int i=1;i<n;i++) {
for (int j=1;j<n;j++) {
while (a[i][j]--) equ[j][i]-=1.0/d[i];
}
}
equ[1][n+1]=1; equ[n][n+1]=1;
for (int i=1;i<=n;i++) {
if (abs(equ[i][i])<eps) {
for (int j=i+1;j<=n;j++) {
if (abs(equ[j][i])>eps) {
for (int k=1;k<=n+1;k++) swap(equ[i][k],equ[j][k]);
break;
}
}
}
for (int j=i+1;j<=n;j++) {
if (abs(equ[j][i])<eps) continue;
double t=equ[j][i]/equ[i][i];
for (int k=i;k<=n+1;k++) {
equ[j][k]-=t*equ[i][k];
}
}
}
for (int i=n;i>=1;i--) {
double t=1.0/equ[i][i];
for (int j=i;j<=n+1;j++) equ[i][j]*=t;
x[i]=equ[i][n+1];
for (int j=i+1;j<=n;j++) {
x[i]-=equ[i][j]*x[j];
}
}
for (int i=1;i<=m;i++) {
if (u[i]!=n) p[i]+=x[u[i]]/d[u[i]];
if (v[i]!=n) p[i]+=x[v[i]]/d[v[i]];
}
sort(p+1,p+m+1);
double ans=0;
for (int i=1;i<=m;i++) ans+=p[i]*(m-i+1);
printf("%.3Lf",ans);
return 0;
}