BZOJ 3143 Luogu P3232 [HNOI2013]游走 (DP、高斯消元)

题目链接: (bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=3143
(luogu) https://www.luogu.org/problemnew/show/P3232

题解: 水题。考虑如何求每个点的期望经过次数: 要求\(1\)号点开始\(n\)号点结束，那么\(1\)号点一定一上来就会经过一次，\(n\)号点一共只会经过\(1\)次。因此对于\(1\)到\(n-1\)的每一个点可以列出一个方程，其中\(1\)号点的方程是\(f[1]=\sum_{edge(u,1),1\le u\le n-1} \frac{f[u]}{du[u]}+1\) (\(du\)为度数), 其余点\(v\)的方程是\(f[v]=\sum_{edge(u,v),1\le u\le n-1} \frac{f[u]}{du[u]}\). 这个方程组有\((n-1)\)个未知数\((n-1)\)个方程，解出来即可。\(n\)号点怎么办？如果列出来其实应该是\(f[n]=\sum_{edge(u,n)} \frac{f[u]}{du[u]}=1\), 但是发现这个方程等价于前\((n-1)\)个方程加起来，所以就不用管了。
我们得到了每个点的期望经过次数，然后就可以轻易得到每条边期望经过次数，对于边\((u,v)\)其期望经过次数为\(\frac{f[u]}{du[u]}+\frac{f[v]}{du[v]}\), 其中\(f[n]\)视为\(0\). 根据期望的线性性，总得分期望就等于每条边期望经过次数乘以边权再求和，所以根据排序不等式给期望次数越小的边安排越大的边权即可。

时间复杂度\(O(n^3+m\log m)\).

代码

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> using namespace std;inline int read() {int x=0; bool f=1; char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');if(f) return x;return -x; }const int N = 500; namespace Gauss {double a[N+3][N+3],b[N+3],sol[N+3];void gauss(int n){for(int i=1; i<=n; i++){if(a[i][i]==0){bool found = false;for(int j=i+1; j<=n; j++){if(a[i][j]!=0){for(int k=i; k<=n; k++) swap(a[i][k],a[j][k]);swap(b[j],b[i]);found = true; break;}}if(!found) continue;}for(int j=i+1; j<=n; j++){if(a[j][i]!=0){double coe = -a[j][i]/a[i][i];for(int k=i; k<=n; k++) {a[j][k] += coe*a[i][k];}b[j] += coe*b[i];}}}for(int i=n; i>=1; i--){for(int j=i+1; j<=n; j++){b[i] -= a[i][j]*sol[j];}sol[i] = b[i]/a[i][i];}} } struct AEdge {int u,v; } e[N*N+3]; int du[N+3]; double f[N+3]; double coe[N*N+3]; int permu[N*N+3]; int n,m,en;bool cmp(int x,int y) {return coe[x]>coe[y];}int main() {scanf("%d%d",&n,&m);for(int i=1; i<=m; i++){scanf("%d%d",&e[i].u,&e[i].v);du[e[i].u]++; du[e[i].v]++;}for(int i=1; i<n; i++) Gauss::a[i][i] = -1.0;for(int i=1; i<=m; i++){int u = e[i].u,v = e[i].v;if(u==n || v==n) continue;Gauss::a[u][v] += 1.0/du[v]; Gauss::a[v][u] += 1.0/du[u];}Gauss::b[1] = -1.0;Gauss::gauss(n-1);for(int i=1; i<n; i++) f[i] = Gauss::sol[i];for(int i=1; i<=m; i++){int u = e[i].u,v = e[i].v;coe[i] = f[u]/du[u]+f[v]/du[v];}for(int i=1; i<=m; i++) permu[i] = i;sort(permu+1,permu+m+1,cmp);double ans = 0.0;for(int i=1; i<=m; i++) {ans += coe[permu[i]]*i;}printf("%.3lf\n",ans);return 0; }

总结

以上是生活随笔为你收集整理的BZOJ 3143 Luogu P3232 [HNOI2013]游走 (DP、高斯消元)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。