链接：
题意：
和上次考试 T4 的简化且无修改一样，经典图上高斯消元求期望。
分析：
要求出每个点的期望出发次数 \(f_i\)，每个点度数为 \(d_i\)，有
\[f1=\sum\dfrac{f_v}{d_v}+1,f_u=\sum\dfrac{f_v}{d_v},f_n=0 \]高斯消元即可。那么一条边 \((u,v)\) 的贡献就是 \((\dfrac{f_u}{d_u}+\dfrac{f_v}{d_v})*i\)。
考虑算出每条边的 \((\dfrac{f_u}{d_u}+\dfrac{f_v}{d_v})\)，记为 \(w_i\)，然后有一个容易猜的贪心结论是将 \(w_i\) 从小到大排序，然后逐个乘上 \(m-i+1\)，也就是正序乘倒序时，答案最小。
算法：
利用$$f1=\sum\dfrac{f_v}{d_v}+1,f_u=\sum\dfrac{f_v}{d_v},f_n=0$$，高斯消元算出每个点的期望出发次数，然后转化为边的期望经过次数，最后再排序。时间复杂度 \(O(n^3+m\log m)\)
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
inline int read(){
int p=0,f=1;
char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return p*f;
}
const int N=505;
const int M=125005;
int n;
struct matrix{
int x,y;
double a[N][N];
}A,B;
matrix operator*(const matrix &a,const matrix &b){
matrix c;
for(int i=1;i<=a.x;i++)
for(int j=1;j<=b.y;j++)
c.a[i][j]=0;
c.x=a.x,c.y=b.y;
for(int i=1;i<=a.x;i++)
for(int j=1;j<=b.y;j++)
for(int k=1;k<=a.y;k++)
c.a[i][j]+=a.a[i][k]*b.a[k][j];
return c;
}
matrix matinv(matrix &a){
matrix c;c.x=n,c.y=n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
c.a[i][j]=(i==j);
for(int i=1;i<=n;i++){
int now=i;
for(int j=i+1;j<=n;j++)
if(fabs(a.a[j][i])>fabs(a.a[now][i]))now=j;
swap(a.a[i],a.a[now]);swap(c.a[i],c.a[now]);
double div=a.a[i][i];
for(int j=1;j<=n;j++)
a.a[i][j]/=div,c.a[i][j]/=div;
for(int j=1;j<=n;j++){
if(j==i)continue;
div=a.a[j][i];
for(int k=i;k<=n;k++)
a.a[j][k]-=div*a.a[i][k];
for(int k=1;k<=n;k++)
c.a[j][k]-=div*c.a[i][k];
}
}
return c;
}
int m,q;
int d[N];
int u[M],v[M];
double as[M];
signed main(){
n=in,m=in;
for(int i=1;i<=m;i++)
u[i]=in,v[i]=in,
d[u[i]]++,d[v[i]]++;
A.x=n,A.y=n;
for(int i=1;i<=m;i++)
A.a[u[i]][v[i]]=-1.0/d[v[i]],
A.a[v[i]][u[i]]=-1.0/d[u[i]];
for(int i=1;i<=n;i++)
A.a[n][i]=A.a[i][n]=0.0,A.a[i][i]=1.0;
int tmp=1;
B.a[1][1]=1.0;
B.x=n,B.y=tmp;
A=matinv(A);
B=A*B;
double ans=0;
for(int i=1;i<=m;i++)
as[i]=B.a[u[i]][1]/d[u[i]]+B.a[v[i]][1]/d[v[i]];
sort(as+1,as+1+m);
for(int i=1;i<=m;i++)
ans+=i*as[m-i+1];
printf("%.3lf",ans);
return 0;
}
题外话：
用上次的代码改了改就过了