[HNOI2013]遊走【高斯消元】【機率期望】

傳送門

被坑慘了，，這道題要管的是每個點會被走多少次，然後算邊。

是以出點要乘上的機率是出點的出度分之1.而不是我的出度。每條邊的期望次數肯定是兩個端點各自期望次數*各自的出度分之1。

然後就是個闆子，，日，代碼醜

#include<bits/stdc++.h>
using namespace std;
#define in read()
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;
		ch=getchar();
	}return cnt*f;
}
double mapp[503][503];double ans[503];
struct node{
	double ans;int id;
}a[250003];
int n,m;
struct bili{
	int u,v;
}edge[250003];
int cd[503];
bool cm(node a,node b){
	return a.ans<b.ans;
}
void guess(){
	for(int i=1;i<=n;i++){
		double tem=mapp[i][i];int now=i;
		for(int j=i+1;j<=n;j++)if(fabs(mapp[j][i])>fabs(mapp[now][i]))now=j;
		if(now!=i)swap(mapp[i],mapp[now]);
		for(int j=i;j<=n+1;j++){
			mapp[i][j]/=tem;
		}
		for(int j=i+1;j<=n;j++){
			tem=mapp[j][i];
			for(int k=i;k<=n+1;k++)
				mapp[j][k]-=tem*mapp[i][k];
		}
	}
	ans[n]=mapp[n][n+1];
	for(int i=n-1;i>=1;i--){
		ans[i]=mapp[i][n+1];
		for(int j=i+1;j<=n;j++)ans[i]-=ans[j]*mapp[i][j];
	}
	
}
int first[503],nxt[250003],to[250003],tot;
void add(int a,int b){
	nxt[++tot]=first[a];first[a]=tot;to[tot]=b;
}
signed main(){
	n=in;m=in;
	for(int i=1;i<=m;i++){
		int a=in;int b=in;cd[a]++;cd[b]++;add(a,b);add(b,a);
		//mapp[a][b]--;mapp[b][a]--;mapp[a][a]++;mapp[b][b]++;
		edge[i]={a,b};
	}
	for(int i=1;i<n;i++){
		mapp[i][i]=1;
		for(int j=first[i];j;j=nxt[j]){
			int v=to[j];if(v!=n)mapp[i][v]-=1.0/cd[v];
		}
	}
	for(int i=1;i<=n;i++)mapp[i][n]=0;
	mapp[1][n+1]+=1;for(int i=1;i<=n+1;i++)mapp[n][i]=0;
	mapp[n][n]=1;
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n+1;j++){if(mapp[i][j]>=0)cout<<" "<<(int)mapp[i][j]<<" ";else cout<<(int)mapp[i][j]<<" ";
//		}cout<<endl;
//	}
	guess();
//
	//for(int i=1;i<=n;i++)printf("%.3lf ",ans[i]);cout<<endl;
	for(int i=1;i<=m;i++){
		int u=edge[i].u,v=edge[i].v;if(u>v)swap(u,v);
		double x=ans[u]/(double)cd[u];
		if(v!=n)x+=ans[v]/(double)cd[v]; 
		a[i].ans=x;a[i].id=i;
	}
	sort(a+1,a+m+1,cm);
	double Ans=0;
	for(int i=1;i<=m;i++){
		Ans+=(double)(m-i+1)*a[i].ans;
	}printf("%.3lf",Ans);
	return 0;
}