C++14(g++5.4) 解法, 执行用时: 385ms, 内存消耗: 3740K, 提交时间: 2019-10-17 15:09:17

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-8;
const int maxn = 510,maxm=250010;
int n,m;
typedef double Matrix[maxn][maxn];
int d[maxn];
double ans[maxm],res[maxn];
Matrix A;
struct edge{
	int u,v; 
}e[maxm];

void gauss_jordan(Matrix A, int n)
{
	int i,j,k,r;
	for (i = 0; i < n; i++)
	{
		r = i;
		for (j = i + 1; j < n; j++)
			if (fabs(A[j][i]) > fabs(A[r][i])) r = j;
		if (fabs(A[r][i]) < eps) continue;
		if (r != i) for (j = 0; j <= n; j++) swap(A[r][j], A[i][j]);

		for (k = 0; k < n; k++) if(k!=i)
			for (j = n; j >= i ; j--)
				A[k][j] -= A[k][i] / A[i][i] * A[i][j];
	}
}
bool cmp(double x,double y)
{
	return x>y;
}
int main() 
{
	scanf("%d%d",&n,&m);
	n--;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&e[i].u,&e[i].v);
		e[i].u--;e[i].v--;
		d[e[i].u]++;d[e[i].v]++;
	}
	for(int i=1;i<=m;i++)
	{
		if(e[i].v!=n)	A[e[i].u][e[i].v]-=1.0/d[e[i].v];
		if(e[i].u!=n)	A[e[i].v][e[i].u]-=1.0/d[e[i].u];
	}
	for(int i=0;i<n;i++)	A[i][i]=1;
	A[0][n]=1;
	gauss_jordan(A,n);
	for(int i=0;i<n;i++)    res[i]=A[i][n]/A[i][i];
	for(int i=1;i<=m;i++)    ans[i]=res[e[i].u]/d[e[i].u]+res[e[i].v]/d[e[i].v];
	sort(ans+1,ans+m+1,cmp);
	double sum=0;
	for(int i=1;i<=m;i++)	sum+=ans[i]*i;
	printf("%.3lf\n",sum);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 109ms, 内存消耗: 4708K, 提交时间: 2020-04-03 13:17:06

#include<bits/stdc++.h>
using namespace std;
const int N=505;
double a[N][N],p[N*N];
int u[N*N],v[N*N],du[N];
vector<int>g[N];
double x[N];
int n,m;
void guass(int n)
{
	for(int i=1;i<=n;i++)
	{
		int k=i;
		for(int j=i;j<=n;j++)
		if(fabs(a[j][i])>fabs(a[k][i]))
		k=j;
		swap(a[i],a[k]);
		for(int j=1;j<=n;j++)
		if(j!=i)
		{
			double c=a[j][i]/a[i][i];
			for(int k=i;k<=n+1;k++)
			a[j][k]-=c*a[i][k];
		 } 
	}
	for(int i=1;i<=n;i++)
	x[i]=a[i][n+1]/a[i][i];
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>u[i]>>v[i];
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
		du[u[i]]++,du[v[i]]++;
	}
	for(int i=1;i<n;i++)
	{
		a[i][i]=1;
		for(auto v:g[i])
		if(v!=n) a[i][v]-=1.0/du[v];
	}
	a[1][n]=1;
	guass(n-1);
	for(int i=1;i<=m;i++)
	p[i]=x[u[i]]/du[u[i]]+x[v[i]]/du[v[i]];
	sort(p+1,p+m+1);
	double ans=0;
	for(int i=1;i<=m;i++)
	ans+=i*p[m-i+1];
	printf("%.3lf\n",ans);
	return 0;
}