P3232 [HNOI2013] 游走

考虑贪心。

随机游走则显然每条边期望经过次数越大则其编号应越小。

每条边的期望经过次数难以计数，考虑每个店期望经过次数，设计状态 \(f_i\) 表示点 \(i\) 期望经过次数。

转移：

\(f_i=\sum_{v\in e_i}f_v\cdot \frac{f_v}{d_v}+[u=1]\)

其中 \(d_i\) 为点 \(i\) 的度数，而 \([u=1]\) 则是因为初始在 1 也算一次经过次数，\(f_n\)。

而这种方程无法按照某种顺序转移，发现 \(n\le 500\) 考虑高斯消元，把每个 \(f_i\) 当做一个未知数，则为 \(n\) 个 \(n\) 元方程组，直接 \(O(n^3)\) 求解。

#include<bits/stdc++.h>
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
using namespace std;
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define ll long long
#define ull unsigned long long
#define intz(x,y) memset((x),(y),sizeof((x)))
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline ll read(){ll x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-')f=-1;ch=nc();}while(ch>=48&&ch<=57)x=x*10+ch-48,ch=nc();return x*f;
}
void write(pii x){cout<<x.fi<<' '<<x.se<<'\n';}
void write(vector<auto>x){for(auto i:x)cout<<i<<' ';cout<<'\n';}
inline int pcount(ll x){for(int i=0,res=0;;res+=(x>>i)&1,i++)if(i>60)return res;
}
inline ll lowbit(ll x){return x&-x;}
const int N=505,M=2e5+5;
int n,m,d[N],_u[M],_v[M],E[M];double ans,a[N][N];vector<int>e[N];
void add(int u,int v){e[u].pb(v),e[v].pb(u);}
double calc(int i){int u=_u[i],v=_v[i];return (u==n?0:a[u][n+1]/d[u])+(v==n?0:a[v][n+1]/d[v]);
}
inline void UesugiErii(){cin>>n>>m;for(int i=1;i<=m;i++)cin>>_u[i]>>_v[i],++d[_u[i]],++d[_v[i]],add(_u[i],_v[i]);for(int i=1;i<=n;a[i][i]=1,i++)if(i<n)for(int v:e[i])a[i][v]=-1.0/d[v];a[1][n+1]=1;for(int i=1;i<n;i++){double mx=0;int id=0;for(int j=i;j<n;j++)if(abs(a[j][i])>mx)mx=abs(a[j][i]),id=j;for(int j=i;j<=n+1;j++)swap(a[i][j],a[id][j]);for(int j=i+1;j<=n+1;j++)a[i][j]/=a[i][i];a[i][i]=1;	for(int j=i+1;j<n;j++){for(int k=i+1;k<=n+1;k++)a[j][k]-=a[j][i]*a[i][k]; a[j][i]=0;}}for(int i=n;i;i--)for(int j=i+1;j<=n;j++)a[i][n+1]-=a[j][n+1]*a[i][j];for(int i=1;i<=m;i++)E[i]=i;sort(E+1,E+1+m,[&](int x,int y){return calc(x)<calc(y);});for(int i=1;i<=m;i++)ans+=(m-i+1)*calc(E[i]);cout<<fixed<<setprecision(3)<<ans;
}
signed main(){//IO();cfast;int _=1;//cin>>_;for(;_;_--)UesugiErii();return 0;
}