游
走
游走
游走
题目描述见链接 .
正
解
部
分
\color{red}{正解部分}
正解部分
题目要求走过的 边 编号和期望最小,
先求出 点 的期望值
f
[
i
]
f[i]
f[i], 走过一条边
u
,
v
u, v
u,v 的期望值即为
f
[
u
]
/
d
u
[
u
]
+
f
[
v
]
/
d
u
[
v
]
f[u]/du[u] + f[v]/du[v]
f[u]/du[u]+f[v]/du[v], 最后将期望值大的边赋予较小的编号即可 .
现在求 点 的期望值,
f
[
i
]
=
∑
f
[
t
o
]
/
d
u
[
t
o
]
f[i] = \sum f[to]/du[to]
f[i]=∑f[to]/du[to], 依此可以列出
N
N
N 个方程, 高斯消元 解方程即可 .
实
现
部
分
\color{red}{实现部分}
实现部分
与
N
N
N 号点相连的 点, 边 不用计
N
N
N 的贡献 .走到
1
1
1 的实际期望值 为解出的期望
+
1
+1
+1 .
#include<bits/stdc++.h>
#define reg register
int read(){
char c
;
int s
= 0, flag
= 1;
while((c
=getchar()) && !isdigit(c
))
if(c
== '-'){ flag
= -1, c
= getchar(); break ; }
while(isdigit(c
)) s
= s
*10 + c
-'0', c
= getchar();
return s
* flag
;
}
const int maxn
= 505;
const double eps
= 1e-14;
int N
;
int M
;
int num0
;
int du
[maxn
];
int head
[maxn
];
int u
[maxn
*maxn
];
int v
[maxn
*maxn
];
double B
[maxn
*maxn
];
double A
[maxn
][maxn
];
struct Edge
{ int nxt
, to
; } edge
[maxn
*maxn
<<1];
void Add(int from
, int to
){
edge
[++ num0
] = (Edge
){ head
[from
], to
};
head
[from
] = num0
; du
[from
] ++;
}
void Guass(){
for(reg
int i
= 1; i
< N
; i
++){
int max_id
= i
;
for(reg
int j
= i
+1; j
< N
; j
++)
if(fabs(A
[j
][i
]) > fabs(A
[max_id
][i
])) max_id
= j
;
std
::swap(A
[max_id
], A
[i
]);
for(reg
int j
= N
; j
>= i
; j
--) A
[i
][j
] /= A
[i
][i
];
for(reg
int j
= i
+1; j
< N
; j
++){
if(fabs(A
[j
][i
]) < eps
) continue ;
for(reg
int k
= N
; k
>= i
; k
--) A
[j
][k
] -= A
[j
][i
] * A
[i
][k
];
}
}
for(reg
int i
= N
-1; i
>= 1; i
--)
for(reg
int j
= i
+1; j
< N
; j
++) A
[i
][N
] -= A
[j
][N
]*A
[i
][j
];
}
int main(){
N
= read(), M
= read();
for(reg
int i
= 1; i
<= M
; i
++){
u
[i
] = read(), v
[i
] = read();
Add(u
[i
], v
[i
]), Add(v
[i
], u
[i
]);
}
for(reg
int i
= 1; i
< N
; i
++){
A
[i
][i
] = 1;
for(reg
int j
= head
[i
]; j
; j
= edge
[j
].nxt
){
int to
= edge
[j
].to
;
if(to
== N
) continue ;
A
[i
][to
] = -1.0/du
[to
];
}
}
A
[1][N
] = 1;
Guass();
for(reg
int i
= 1; i
<= M
; i
++){
if(u
[i
] != N
) B
[i
] += A
[u
[i
]][N
]/du
[u
[i
]];
if(v
[i
] != N
) B
[i
] += A
[v
[i
]][N
]/du
[v
[i
]];
}
std
::sort(B
+1, B
+M
+1);
double Ans
= 0;
for(reg
int i
= 1; i
<= M
; i
++) Ans
+= B
[i
] * (M
-i
+1);
printf("%.3lf\n", Ans
);
return 0;
}
