比赛 20120613 评测结果 AAAAAAAAAAAAAAAA
题目名称 臭气弹 最终得分 100
用户昵称 ZhouHang 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-06-13 17:33:48
显示代码纯文本
/**
*Prob	: dotp
*Data	: 2012-6-13
*Sol	: 高斯消元
*Author : ZhouHang
*/

#include <cstdio>
#include <cstring>
#include <iomanip>
#include <algorithm>

#define MaxN 310

using namespace std;

int n,i,j,e,y,p,q;
int d[MaxN];
bool map[MaxN][MaxN];
double m[MaxN][MaxN],x[MaxN],b[MaxN];

void doit()
{
	for (int k=1; k<n; k++)
	 for (int i=k+1; i<=n; i++)
	 {
		double t=m[i][k]/m[k][k];
		for (int j=k+1; j<=n; j++)
			m[i][j]-=m[k][j]*t;
		b[i]-=b[k]*t;
	 }
	 
	for (int i=n; i>=1; i--)
	{
		double sum=0;
		for (j=n; j>i; j--)
			sum+=m[i][j]*x[j];
		x[i]=(b[i]-sum)/m[i][i];
	}
}

int main()
{
	freopen("dotp.in","r",stdin);
	freopen("dotp.out","w",stdout);
	

	scanf("%d%d%d%d",&n,&e,&p,&q);
	double tmp=(double)p/q;
	
	int u,v;
	memset(map,false,sizeof(map));
	for (int i=1; i<=e; i++)
	{
		scanf("%d%d",&u,&v);
		d[u]++; d[v]++;
		map[u][v]=true; map[v][u]=true;
	}
	
	b[1]=tmp;
	for (int i=1; i<=n; i++)
	{
		m[i][i]=1;
		for (int j=1; j<=n; j++)
			if (map[i][j]) m[i][j]=-(1-tmp)/d[j];
	}
	
	doit();
	
	for (int i=1; i<=n; i++)
		printf("%.9lf\n",x[i]);
	
	fclose(stdin); fclose(stdout);
	return 0;
}