P3232 [HNOI2013]游走
2022/1/22 23:04:17
本文主要是介绍P3232 [HNOI2013]游走,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
\[\color{royalblue}{\huge\texttt{P3232 [HNOI2013]游走}} \]设
\[f(x) \]表示期望从 \(x\) 点离开的次数,
\[Num_e(x) \]表示 \(x\) 点的出度,
则每条边期望被经过的次数为
推dp柿子:
\[{f(x)=\sum_{v\in edge(x)} \frac{f(v)}{Num_e(v)}}\;,\;x \in (1,n). \]\[{f(x)=\sum_{v\in edge(x)} \frac{f(v)}{Num_e(v)}+1}\;,\;x=1. \]\[{f(x)=0\;,\;x=n.} \]第一个柿子是说,对于 \((1,n)\) 这些点,进入它们后必然出去一次,所以 \(E(into\;\;x)=E(out\;of\;\;x)\).
第二个柿子,对于 \(1\) 号点,从它出发决定了它离开次数比进入次数大 \(1\).
第三个柿子,\(n\) 为终点,不会再离开了.
然后大力高斯消元,把边按期望经过次数排序,贪心选择.
code:
#include <bits/stdc++.h> #define ri register int #define g() getchar() #define MAXN 502 #define pc(a) putchar(a) #define Tp template<typename T> using namespace std; namespace SlowIO { Tp inline void rd(T &x) { x=0;char i=g();bool f=1; while(!isdigit(i)) f&=(i!='-'),i=g(); while(isdigit(i)) x=(x<<3)+(x<<1)+(i^48),i=g(); x*=((f<<1)-1); } Tp inline void op(T x){ if(x<0) pc('-'),x=-x; if(x>=10) op(x/10); pc(x%10+48); } Tp inline void writeln(T x){op(x);pc('\n');} Tp inline void writesp(T x){op(x);pc(' ');} }; using namespace SlowIO; int cntr,head[MAXN]; struct edge{ int to,next; }e[MAXN*MAXN]; inline void add(int u,int v){ e[++cntr].to=v; e[cntr].next=head[u]; head[u]=cntr; } int n,m; int deg[MAXN];//每个点的出度 double a[MAXN][MAXN]; double f[MAXN];//期望从x点离开的次数 E(离开x) double g[MAXN*MAXN]; double ass;//Asswer //x∈(1,n),f[x]=E(进入x点); //f[1]=E(进入1点)+1,f[n]=0. //Gauss-Jordan #define abs fabs inline bool solve() { ri sta; for(ri i=1;i<=n;i++) { sta=i; for(ri j=i+1;j<=n;j++) if(abs(a[j][i])>abs(a[sta][i])) sta=j; if(sta!=i) for(ri j=1;j<=n+1;j++) swap(a[sta][j],a[i][j]); if(!a[i][i]) return true; for(ri j=1;j<=n;j++) { if(j==i) continue; for(ri k=i+1;k<=n+1;k++) a[j][k]-=a[i][k]*a[j][i]/a[i][i]; } } return false; } int main() { rd(n),rd(m); static int u[MAXN*MAXN],v[MAXN*MAXN]; //我焯 我为什么一直开的MAXN啊我sb吗() static int frm,tp; for(ri i=1;i<=m;i++) { rd(u[i]),rd(v[i]); add(u[i],v[i]),add(v[i],u[i]); deg[u[i]]++,deg[v[i]]++; } //我焯 真就遍历所有边呗 O(2m)>O(m)(暴论) a[1][n]=1; for(ri i=1;i<=n-1;i++) { a[i][i]=1.0; for(ri j=head[i];j;j=e[j].next) { int v=e[j].to; if(v==n) continue; a[i][v]=-1.0/deg[v]; } }--n;solve(); for(int i=1;i<=n;i++) f[i]=a[i][n+1]/a[i][i]; for(ri i=1;i<=m;i++){ frm=u[i],tp=v[i]; g[i]+=(frm!=n+1)*f[frm]/deg[frm]+(tp!=n+1)*f[tp]/deg[tp]; } sort(g+1,g+m+1); for(ri i=1;i<=m;i++) ass+=1.0*i*g[m-i+1]; printf("%.3lf",ass); return 0; }
这篇关于P3232 [HNOI2013]游走的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性