记录编号	358919	评测结果	AAAAAAAAAAAAAAAA
题目名称	[USACO Hol10] 臭气弹	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	0.176 s
提交时间	2016-12-19 18:13:28	内存使用	1.38 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 305;
int N, M, P, Q;
int n[maxn][maxn];
double a[maxn][maxn+1];

void calc(int n) {
	for(int i=1; i<=n; ++i) {
		int r = i;
		for(int j=i+1; j<=n; ++j) 
			if(fabs(a[j][i])>fabs(a[r][i])) { r = j; break;}
		if(r!=i) for(int j=1; j<=n+1; ++j) swap(a[r][j], a[i][j]);
		for(int j=1; j<=n; ++j) if(i!=j) {
			double rate = a[j][i]/a[i][i];
			for(int k=1; k<=n+1; ++k) a[j][k] -= a[i][k]*rate;
		}
	}
}

int main() {
	freopen("dotp.in","r",stdin);
	freopen("dotp.out","w",stdout);	
	scanf("%d %d %d %d", &N, &M, &P, &Q);
	for(int i=1, x, y; i<=M; ++i) {
		scanf("%d %d", &x, &y);
		++n[x][y], ++n[y][x];
		++n[x][0], ++n[y][0];
	}

	a[1][N+1] = 1;
	for(int i=1; i<=N; ++i) 
		for(int j=1; j<=N; ++j) {
			if(i==j) a[i][j] = 1;
			else if(n[i][j])
				a[i][j] = -1.0*(Q-P)/Q*n[i][j]/n[j][0];
		}
	calc(N);
	for(int i=1; i<=N; ++i)
		printf("%.9lf\n", a[i][N+1]/a[i][i]*P/Q);
	getchar(), getchar();
	return 0;
}