题目链接
(Solution)
首先申明几个变量：
f[x]:到点x的概率,
vis[x]:x点的度
dp[x][y]:(x,y)这条边的概率
number[x][y]:x这条边的编号
下面的式子保证存在一条(x,y)的边
我们可以知道总分的期望为：
[sum dp[x][y]*number[x][y]
]
即:所有边的期望成这条边的编号的和
那么(dp)数组怎么算呢?
[dp[x][y]=frac{f[x]}{vis[x]}+frac{f[y]}{vis[y]}
]
所以我们现在的任务就是求出(f)数组
再来看看(f)数组怎么求?
[p[x]=sumfrac{p[y]}{vis[y]}
]
发现这个式子并不能简单的递推,因为存在环.
于是我们可以列方程接未知数
运用高斯消元就好了.
但是注意:
- 如果有点和(n)相连,那么在计算期望时不需要算,因为到了点(n)时不会继续走下去了
- 因为开始就在点(1)，所以第一个方程的结果要设为(1)
解出方程后便可以将(dp)数组算出来了.
现在考虑原问题: "现在，请你对这M条边进行编号，使得小Z获得的总分的期望值最小"
我们可以进行贪心
将期望大的边使他编号小
(Code)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
struct node{
int to,next;
}e[5000010];
int vis[5000010],head[10000001],n,m,cnt,X[1000001],Y[10000001];
void add(int x,int y){
e[++cnt].to=y,e[cnt].next=head[x],head[x]=cnt;
}
double a[5001][5001],f[1000001],ans=0;
void Gauss(){
n--,a[1][n+1]=-1;
for(int i=1; i<=n; i++) {
int bj=i;
for(int j=i+1; j<=n; j++)
if(fabs(a[j][i])>fabs(a[bj][i]))
bj=j;
for(int j=1; j<=n+1; j++)
swap(a[bj][j],a[i][j]);
if(!a[i][i])
continue;
double p=a[i][i];
for(int j=1;j<=n+1;j++)
a[i][j]/=p;
for(int j=1;j<=n;j++)
if(i!=j){
double o=a[j][i];
for(int k=1;k<=n+1;k++)
a[j][k]-=a[i][k]*o;
}
}
for(int i=n-1; i>=1; i--)
for(int j=i+1; j<=n; j++)
a[i][n+1]-=a[j][n+1]*a[i][j];
}
int main() {
n=read(),m=read();
for(int i=1;i<=m;i++)
X[i]=read(),Y[i]=read(),add(Y[i],X[i]),add(X[i],Y[i]),vis[X[i]]++,vis[Y[i]]++;
for(int i=1;i<n;i++){
a[i][i]=-1;
for(int j=head[i];j;j=e[j].next){
int v=e[j].to;
if(v!=n)
a[i][v]=1.0/vis[v];
}
}
Gauss();
for(int i=1; i<=m; i++){
if(X[i]!=n+1)
f[i]+=a[X[i]][n+1]/vis[X[i]];
if(Y[i]!=n+1)
f[i]+=a[Y[i]][n+1]/vis[Y[i]];
}
sort(f+1,f+1+m);
for(int i=1;i<=m;i++)
ans+=f[i]*(m-i+1);
printf("%0.3lf",ans);
return 0;
}