然后就可以高斯消元求解了
代码 #include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<queue> inline int read(){ int x=0,fh=1; char ch=getchar(); while(ch<\'0\' || ch>\'9\'){ if(ch==\'-\') fh=-1; ch=getchar(); } while(ch>=\'0\' && ch<=\'9\'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*fh; } const int maxn=505,maxm=125005; const double eqs=1e-10; int n,m,head[maxn],tot=1; struct asd{ int from,to,next; }b[maxm<<1]; void ad(int aa,int bb){ b[tot].from=aa; b[tot].to=bb; b[tot].next=head[aa]; head[aa]=tot++; } int du[maxn]; double mp[maxn][maxn],ans[maxn]; void gsxy(){ int now=1; for(int i=1;i<=n;i++){ double mmax=0; int jl; for(int j=now;j<=n;j++){ if(std::fabs(mmax)<std::fabs(mp[j][i])){ mmax=mp[j][i]; jl=j; } } if(std::fabs(mmax)<eqs) continue; if(jl!=now) std::swap(mp[jl],mp[now]); for(int j=i+1;j<=n+1;j++){ mp[now][j]/=mp[now][i]; } mp[now][i]=1.0; for(int j=now+1;j<=n;j++){ double cs=mp[j][i]; for(int k=i;k<=n+1;k++){ mp[j][k]-=mp[now][k]*cs; } } now++; } ans[n]=mp[n][n+1]; for(int i=n-1;i>=1;i--){ ans[i]=mp[i][n+1]; for(int j=i+1;j<=n;j++){ ans[i]-=ans[j]*mp[i][j]; } } } std::priority_queue<double> q; int main(){ memset(head,-1,sizeof(head)); n=read(),m=read(); for(int i=1;i<=m;i++){ int aa,bb; aa=read(),bb=read(); ad(aa,bb); ad(bb,aa); du[aa]++; du[bb]++; } for(int i=1;i<=n;i++){ for(int j=head[i];j!=-1;j=b[j].next){ int u=b[j].to; if(u==n) continue; mp[i][u]=-1.0/du[u]; } } for(int i=1;i<=n;i++){ mp[i][i]=1; } for(int i=1;i<n;i++){ mp[n][i]=0; } mp[n][n]=1; mp[n][n+1]=1; mp[1][n+1]=1; gsxy(); for(int i=1;i<tot;i+=2){ int aa=b[i].from; int bb=b[i].to; q.push((double)(ans[aa]/du[aa]*(aa!=n)+ans[bb]/du[bb]*(bb!=n))); } double nans=0; for(int i=1;i<=m;i++){ if(!q.empty()){ nans+=q.top()*i; q.pop(); } } printf("%.3f\n",nans); return 0; } 10、洛谷P4284 [SHOI2014]概率充电器 题目描述题目传送门
分析我们设 \(f[u]\) 为节点 \(u\) 不被点亮的概率
那么需要满足 \(u\) 既不会自己点亮自己，也不会被与它相邻的点点亮
我们可以任选一个点作为根节点，求出节点 \(u\) 只被儿子节点影响的概率
然后再通过换根 \(DP\) 求出以其它节点为根的情况
代码 #include<cstdio> #include<cstring> const int maxn=1e6+5; int head[maxn],tot=1,n; struct asd{ int to,next; double val; }b[maxn]; void ad(int aa,int bb,int cc){ b[tot].to=bb; b[tot].next=head[aa]; b[tot].val=(double)cc*0.01; head[aa]=tot++; } double f[maxn],p[maxn],g[maxn]; void dfs(int now,int fa){ f[now]=p[now]; for(int i=head[now];i!=-1;i=b[i].next){ int u=b[i].to; if(u==fa) continue; dfs(u,now); f[now]*=(1.0-b[i].val+b[i].val*f[u]); } } void dfs2(int now,int fa,double lat){ if(now==1){ g[now]=f[now]; } else { double P=g[fa]/(1.0-lat+lat*f[now]); g[now]=f[now]*(1.0-lat+lat*P); } for(int i=head[now];i!=-1;i=b[i].next){ int u=b[i].to; if(u==fa) continue; dfs2(u,now,b[i].val); } } int main(){ memset(head,-1,sizeof(head)); scanf("%d",&n); for(int i=1;i<n;i++){ int aa,bb,cc; scanf("%d%d%d",&aa,&bb,&cc); ad(aa,bb,cc); ad(bb,aa,cc); } for(int i=1;i<=n;i++){ int aa; scanf("%d",&aa); p[i]=1.0-(double)aa*0.01; } dfs(1,0); dfs2(1,0,0); double ans=0; for(int i=1;i<=n;i++){ ans+=(1.0-g[i]); } printf("%.6f\n",ans); return 0; } 11、一个人的游戏 分析这道题通过带换系数的方法解决，思路不错
12、Gambling Guide 分析传送门
13、换教室 题目描述题目传送门
分析设 \(f[i][j][0]\) 为截止到第 \(i\) 节课，一共换了 \(j\) 次，其中第 \(i\) 节课没有申请换教室的耗费体力值的最小期望
设 \(f[i][j][1]\) 为截止到第 \(i\) 节课，一共换了 \(j\) 次，其中第 \(i\) 节课申请换教室的耗费体力值的最小期望
状态转移就很简单了
代码 #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> const int maxn=2e3+5; int f[maxn][maxn]; int n,m,e,v,c[maxn],d[maxn]; typedef double db; db k[maxn]; db dp[maxn][maxn][2]; int main(){ memset(f,0x3f,sizeof(f)); scanf("%d%d%d%d",&n,&m,&v,&e); for(int i=1;i<=n;i++){ scanf("%d",&c[i]); } for(int i=1;i<=n;i++){ scanf("%d",&d[i]); } for(int i=1;i<=n;i++){ scanf("%lf",&k[i]); } for(int i=1;i<=v;i++){ f[i][i]=0; } for(int i=0;i<=n;i++){ for(int j=0;j<=m;j++){ dp[i][j][0]=dp[i][j][1]=1e18; } } for(int i=1;i<=e;i++){ int aa,bb,cc; scanf("%d%d%d",&aa,&bb,&cc); if(f[aa][bb]>cc) f[aa][bb]=f[bb][aa]=cc; } for(int kk=1;kk<=v;kk++){ for(int i=1;i<=v;i++){ for(int j=1;j<=v;j++){ f[i][j]=std::min(f[i][j],f[i][kk]+f[kk][j]); } } } dp[1][1][1]=dp[1][0][0]=0; for(int i=2;i<=n;i++){ for(int j=0;j<=std::min(i,m);j++){ if(j)dp[i][j][1]=std::min(dp[i][j][1],dp[i-1][j-1][0]+k[i]*f[c[i-1]][d[i]]+(1-k[i])*f[c[i-1]][c[i]]); if(j)dp[i][j][1]=std::min(dp[i][j][1],dp[i-1][j-1][1]+k[i-1]*k[i]*f[d[i-1]][d[i]]+(1-k[i])*(1-k[i-1])*f[c[i-1]][c[i]]+k[i-1]*(1-k[i])*f[d[i-1]][c[i]]+k[i]*(1-k[i-1])*f[d[i]][c[i-1]]); dp[i][j][0]=std::min(dp[i][j][0],dp[i-1][j][0]+f[c[i]][c[i-1]]); dp[i][j][0]=std::min(dp[i][j][0],dp[i-1][j][1]+k[i-1]*f[d[i-1]][c[i]]+(1-k[i-1])*f[c[i]][c[i-1]]); } } double ans=1e18; for(int i=0;i<=m;i++){ ans=std::min(ans,dp[n][i][0]); ans=std::min(ans,dp[n][i][1]); } printf("%.2f\n",ans); return 0; } 14、跳一跳 题目描述题目传送门
分析设 \(f[i]\) 为当前在 \(i\) 点，到达 \(n\) 点的期望时间
转移很简单，但是注意要把变量滚一下