BZOJ 3143: [Hnoi2013]游走 [概率DP 高斯消元]

一个无向连通图,顶点从1编号到N,边从1编号到M。 
小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。 
现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。

 

输入保证30%的数据满足N≤10,100%的数据满足2≤N≤500且是一个无向简单连通图。


做过一道类似的后感觉比较简单了

求$f[i]$到每个点的概率

$f[i]=\sum\limits_{(i,j) \in E}{f[j]*\frac{1}{d[j]}}$

$f[1]$额外加上$1$

$f[n]=0$因为到$n$后就不走了没必要用$n$的概率

然后就可以得到通过一条边的概率啦,贪心分配即可

然后BZOJ数据太弱了....洛谷的数据在消元时还要判断系数$<eps$

PS:这种题应该保证有解吧

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=;
double eps=1e-;
inline int read(){
char c=getchar();int x=;
while(c<''||c>''){c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x;
}
int n,m,u,v;
int d[N];
double p[N],a[N][N];
struct edge{
int v,ne,u;
}e[N*N<<];
int h[N],cnt=;
inline void ins(int u,int v){
cnt++;
e[cnt].u=u;e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].u=v;e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;
}
void buildEquation(){
for(int i=;i<n;i++){
a[i][i]=;int j;
for(int k=h[i];k;k=e[k].ne) j=e[k].v,a[i][j]=-1.0/d[j];
}
a[][n+]=;
a[n][n]=;a[n][n+]=;
}
void GaussElimination(){
for(int i=;i<=n;i++){
int r=i;
for(int j=i+;j<=n;j++) if(abs(a[j][i])>abs(a[r][i])) r=j;
if(r!=i) for(int k=;k<=n+;k++) swap(a[r][k],a[i][k]);
for(int j=i+;j<=n;j++) if(abs(a[j][i])>eps){
double t=a[j][i]/a[i][i];
for(int k=i;k<=n+;k++) a[j][k]-=t*a[i][k];
}
}
for(int i=n;i>=;i--){
for(int j=n;j>i;j--) a[i][n+]-=a[i][j]*a[j][n+];
a[i][n+]/=a[i][i];
p[i]=a[i][n+];
}
}
double f[N*N];
void solve(){
for(int i=;i<=m;i++){
int u=e[i<<].u,v=e[i<<].v;
f[i]=p[u]/d[u]+p[v]/d[v];
}
sort(f+,f++m);
double ans=;
for(int i=;i<=m;i++) ans+=(m-i+)*f[i];
printf("%.3lf",ans);
}
int main(){
freopen("in","r",stdin);
n=read();m=read();
for(int i=;i<=m;i++) u=read(),v=read(),ins(u,v),d[u]++,d[v]++;
buildEquation();
GaussElimination();
solve();
}
 
 
上一篇:BZOJ_1778_[Usaco2010 Hol]Dotp 驱逐猪猡_概率DP+高斯消元


下一篇:【bzoj1778】[Usaco2010 Hol]Dotp 驱逐猪猡 矩阵乘法+概率dp+高斯消元