題目鏈接: (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、高斯消元)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。