是因为精度问题吗?qwq,我要疯啦!
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int s = 0,f = 1;char c = getchar();
while (!isdigit(c)){if (c == '-')f = -1;c = getchar();}
while (isdigit(c)){s = (s << 3) + (s << 1) + (c ^ 48);c = getchar();}
return s*f;
}
const int N = 5e2 + 5;
const int M = 5e5 + 5;
int n,m,cnt,deg[N];
int head[N];
long double a[N][N],f[N],g[N];
long double ans = 0;
struct node{
int v,next;
}tree[M<<1];
struct side{
int u,v;
}edge[M];
void add(int u,int v){
tree[++cnt].next = head[u];
tree[cnt].v = v;
head[u] = cnt;
}
long double c(long double p){
return p>0?p:-p;
}
void Gauss_Yordan(){
for (int i=1;i<n;i++){
int maxn = i;
for (int j=i+1;j<n;j++)
if (c(a[j][i]) > c(a[maxn][i]))
maxn = j;
swap(a[maxn],a[i]);
for (int j=1;j<n;j++){
if (i == j)
continue;
long double tmp = a[j][i] / a[i][i];//needed to be delete
for (int k=i+1;k<=n;k++)//all the
a[j][k] -= tmp * a[i][k];
}
}
for (int i=1;i<n;i++)
g[i] = 1.0 * a[i][n] / a[i][i];
}
int main()
{
//freopen("P3232_5.in","r",stdin);
n = read(); m = read();
for (int i=1,u,v;i<=m;i++){
u = read(); v = read();
edge[i].u = u; edge[i].v = v;
add(edge[i].u,edge[i].v);
add(edge[i].v,edge[i].u);
++deg[u],++deg[v];
}
for (int i=1;i<n;i++){
a[i][i] = 1.0;
for (int j = head[i];j;j=tree[j].next){
int v = tree[j].v;
if (v != n)
a[i][v] = -1.0 / deg[v];
}
}
a[1][n] = 1.0;
Gauss_Yordan();
for (int i=1;i<=m;i++){
int u = edge[i].u,v = edge[i].v;
if (u != n)
f[i] += 1.0 * g[u] / deg[u] * 1.0;
if (v != n)
f[i] += 1.0 * g[v] / deg[v] * 1.0;
}
sort(f+1,f+m+1);
for (int i=1;i<=m;i++)
ans += (long double)(m - i + 1)*1.0*f[i];
printf("%.3Lf\n",ans);
return 0;
}