记录编号	425432	评测结果	AAAAAAAAAA
题目名称	[HNOI 2013]游走	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	0.155 s
提交时间	2017-07-15 10:19:37	内存使用	2.45 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,cnt;
double a[505][505],b[505],f[505],hh[250005],to[505],lu[505][505];
void init()
{
	for(int i=1;i<=n;i++)
	{
	   a[i][i]=1;
	   for(int j=1;j<n;j++)
	      if(lu[j][i])
	          a[i][j]-=(double)(lu[j][i]/to[j]);
	}
	b[1]=1;
}
void GS()
{
	int im,num=1;
	for(int i=1;i<n;i++,num++)
	{
		im=i;
		for(int j=i+1;j<=n;j++)
		    if(fabs(a[j][i])>fabs(a[im][i]))
		        im=j;
		if(im!=i)
		{
			for(int j=1;j<=n;j++)
			    swap(a[i][j],a[im][j]);
			swap(b[i],b[im]);
		}
		if(!a[num][i]){num--;continue;}
		for(int j=num+1;j<=n;j++)
		{
			if(!a[num][j])continue;
			double t=a[j][i]/a[num][i];
			for(int k=i+1;k<=n;k++) 
			   a[j][k]-=a[i][k]*t;
			b[j]-=b[i]*t;
		}
	}
	for(int i=n;i>=1;i--)
	{
		for(int j=n;j>i;j--)
		   b[i]-=a[i][j]*f[j];
		f[i]=b[i]/a[i][i];
	}
}
int yjn()
{
	freopen("walk.in","r",stdin);
	freopen("walk.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		lu[x][y]++;
		lu[y][x]++;
		to[x]++;to[y]++;
	}
	init();
	GS();
    for(int i=1;i<n;i++)
	   for(int j=i+1;j<=n;j++)
	      if(lu[i][j])
	      {
		     ++cnt;
			 hh[cnt]=f[i]/to[i];
		     if(j==n)continue;
			 hh[cnt]+=f[j]/to[j];		
		  }
	sort(hh+1,hh+m+1);
	double k=0;
	for(int i=1;i<=m;i++)
	    k+=hh[i]*(m-i+1);
	printf("%.3f",k);
}
int qty=yjn();
int main(){;}