记录编号	469391	评测结果	AAAAAAAAAAAAAAAA
题目名称	[USACO Hol10] 臭气弹	最终得分	100
用户昵称	yymxw	是否通过	通过
代码语言	C++	运行时间	0.182 s
提交时间	2017-11-03 08:34:39	内存使用	1.54 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#define eps 1e-10
using namespace std;
int n,m,x,y,du[400];
double p,q;
double a[400][400],sum=0;
vector<int> son[400];
void gauss()
{
	for(int i=1;i<=n;++i)
	{
		int d=i;
		for(int j=i+1;j<=n;++j)
		  if(fabs(a[j][i])>fabs(a[d][i]))
		    d=j;
		for(int j=1;j<=n+1;++j)  swap(a[d][j],a[i][j]);
	  if(fabs(a[i][i])<eps) continue;
	  double xuan=a[i][i];
	  for(int j=1;j<=n+1;++j)  a[i][j]/=xuan;
	  for(int j=1;j<=n;++j)
	    if(i!=j)
	    {
	    	double xuan=a[j][i];
	    	for(int k=1;k<=n+1;++k)  a[j][k]-=a[i][k]*xuan;
	    }
	}
}
int main()
{
	freopen("dotp.in","r",stdin);
	freopen("dotp.out","w",stdout);
	scanf("%d%d%lf%lf",&n,&m,&p,&q);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		son[x].push_back(y);
		son[y].push_back(x);
		du[x]++;du[y]++;
	}
	for(int i=1;i<=n;++i)
	{
		a[i][i]+=1;
		for(int j=0;j<son[i].size();++j)
			a[i][son[i][j]]-=(1.0-p/q)*1.0/du[son[i][j]];
	}
	a[1][n+1]+=1.0-p/q;
	gauss();
	for(int i=1;i<=n;++i)  sum+=a[i][n+1];
	for(int i=1;i<=n;++i)
	{
		double ans=a[i][n+1]/sum;
		printf("%.9lf\n",ans);
	}
	return 0;
}