@ysner
2018-03-30T17:21:19.000000Z
字数 1767
阅读 2054
期望
高斯消元
一个无向连通图,顶点从1编号到N,边从1编号到M。 小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。 现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。
要使值最小,就让经过越大的边标号越小。
那么就要求边的概率。
设为点概率,为边概率,为点度数。
则
于是要求点的概率。
点的概率为相邻点转移到自己的概率。
即
待会,求当前点概率就要用到邻点概率,求邻点概率就要用到当前点概率,这没法DP啊。
但我们可以发现一个表达式:()
(出发点自身就有概率为1)
这不很像一个一元一次方程?据此可解得。
还有些细节,代码里应该有注释。
// luogu-judger-enable-o2
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=600;
int n,m,h[N*N<<1],cnt,in[N],st[N*N<<1],ed[N*N<<1];
double dp[N][N],ans,x[N],E[N*N<<1];
struct Edge
{
int to,next;
}e[N*N<<1];
il void add(re int u,re int v)
{
e[++cnt]=(Edge){v,h[u]};h[u]=cnt;
}
il int gi()
{
re int x=0,t=1;
re char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il void Gauss()
{
fp(i,1,n)
fp(j,i+1,n)
fq(k,n+1,i) dp[j][k]-=dp[i][k]*dp[j][i]/dp[i][i];
fq(i,n,1)
{
x[i]=dp[i][n+1];
fq(j,n,i+1) x[i]-=dp[i][j]*x[j];
x[i]/=dp[i][i];
}
}
int main()
{
memset(h,-1,sizeof(h));
n=gi();m=gi();
fp(i,1,m)
{
re int u=gi(),v=gi();add(u,v);add(v,u);in[u]++;in[v]++;st[i]=u;ed[i]=v;
}
fp(i,1,n-1)
{
dp[i][i]=1;
for(re int j=h[i];j+1;j=e[j].next)
{
re int v=e[j].to;//j->i???
if(v!=n) dp[i][v]-=1.0/in[v];//概率不能从n转移,写1.0而不是1!!!
}
}
dp[1][n+1]=1;//钦定第一个点概率为1
dp[n][n]=1;
Gauss();
fp(i,1,m) E[i]=x[st[i]]/in[st[i]]+x[ed[i]]/in[ed[i]];
sort(E+1,E+1+m);
fp(i,1,m) ans+=E[i]*(m-i+1);
printf("%.3lf\n",ans);
return 0;
}