记录编号	253056	评测结果	AAAAAWAWWW
题目名称	电子碰撞	最终得分	60
用户昵称	Satoshi	是否通过	未通过
代码语言	C++	运行时间	0.108 s
提交时间	2016-04-21 16:48:50	内存使用	60.68 MiB

#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
#define N 22
#define M 100010
using namespace std;
typedef long double ld;
ifstream cin("electrics.in");
ofstream cout("electrics.out");
int n,m,s,t;
ld p[N]={0};
vector<int> G[N];
ld f[N][M];
ld g[N][M];
ld degree[N]={0};
ld S[N][M];
ld sum[N]={0};
int ans[N]={0};
void read()
{
	int i,u,v;
	cin>>n>>m>>s>>t;
	for(i=1;i<=m;i++)
	{
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
		degree[u]++;
		degree[v]++;
	}
	for(i=1;i<=n;i++)cin>>p[i];
}
bool com(int i,int j)
{
	return sum[i]>sum[j];
}
void work()
{
	int i,j,u,v,T;
	ld solo=0;
	f[s][0]=1;
	g[t][0]=1;
	//for(i=1;i<=n;i++)cout<<(1-p[i])/degree[i]<<endl;
	//for(T=1;T<=10000;T++)for(i=1;i<=n;i++)s[T][i]=0;
	for(T=1;T<=10000;T++)
	{
	    for(i=1;i<=n;i++)
	    {
		    u=i;
			f[u][T]+=(1-S[u][T-1])*f[u][T-1]*p[u];
			g[u][T]+=(1-S[u][T-1])*g[u][T-1]*p[u];
		    for(j=0;j<G[u].size();j++)
		    {
			    v=G[u][j];
				f[v][T]+=(1-S[u][T-1])*f[u][T-1]*(1-p[u])/degree[u];
				g[v][T]+=(1-S[u][T-1])*g[u][T-1]*(1-p[u])/degree[u];
		    }
	    }
		for(i=1;i<=n;i++)S[i][T]=f[i][T]*g[i][T];
	}
	for(T=1;T<=10;T++)
	{
		for(i=1;i<=n;i++)
		{
			sum[i]+=S[i][T];
			//cout<<S[i][T]<<' ';
		}
		//cout<<endl;
	}
	//for(i=1;i<=n;i++)cout<<sum[i]<<endl;
	for(i=1;i<=n;i++)ans[i]=i;
	sort(ans+1,ans+n+1,com);
	for(i=1;i<=n;i++)cout<<ans[i]<<endl;
	/*for(T=0;T<=10000;T++)
	{
		for(i=1;i<=n;i++)
		{
			ans[i]+=f[i][T]*g[i][T];
			cout<<f[i][T]*g[i][T]<<' ';
		}
		cout<<endl;
	}
	for(i=1;i<=n;i++)cout<<ans[i]<<' ';
	cout<<endl;*/
}
int main()
{
	read();
	work();
	return 0;
}