记录编号	101417	评测结果	AAAAAAAAAAAAAAAA
题目名称	[USACO Hol10] 臭气弹	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.462 s
提交时间	2014-05-12 12:32:02	内存使用	1.05 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int SIZEN=310;
const double eps=1e-10;
double A[SIZEN][SIZEN]={0};//A[i][0]存常数
vector<int> c[SIZEN];
int N,M,P,Q;
double stand;//停在某个点的概率
double delta;//不停的概率/停的概率
void Gauss_Jordan(void){
	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;
		if(r!=i) for(int j=0;j<=N;j++) swap(A[r][j],A[i][j]);
		for(int k=1;k<=N;k++){
			if(k==i) continue;
			for(int j=N+1;j>=i;j--) A[k][j]-=A[k][i]/A[i][i]*A[i][j];
		}
	}
}
void work(void){
	for(int i=1;i<=N;i++){
		if(A[i][i]==0) printf("%.9lf\n",0.0);
		else printf("%.9lf\n",A[i][N+1]/A[i][i]);
	}
}
void makeequ(void){
	//基本思路是:设最后污染i的概率为变量
	//可以先写出"第k步污染i"形式的方程作参考
	for(int i=1;i<=N;i++){
		A[i][i]=1;//等式左端"污染i的概率"
		for(int j=0;j<c[i].size();j++){//计算概率的所有项,常数移到右边
			//概率的这一项是:污染x的概率*delta*走到i的概率*stand
			int x=c[i][j];
			double temp=delta*1.0/c[x].size()*stand;//如果有重边自然会多算
			A[i][x]-=temp;
		}
	}
	A[1][N+1]+=stand;
}
void read(void){
	scanf("%d%d%d%d",&N,&M,&P,&Q);
	stand=(P+0.0)/(Q+0.0);
	delta=(Q-P+0.0)/(P+0.0);
	for(int i=1;i<=M;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		c[a].push_back(b);
		c[b].push_back(a);
	}
}
int main(){
	freopen("dotp.in","r",stdin);
	freopen("dotp.out","w",stdout);
	read();
	makeequ();
	//for(int i=1;i<=N;i++){for(int j=1;j<=N+1;j++) cout<<A[i][j]<<" ";cout<<endl;}
	Gauss_Jordan();
	work();
	return 0;
}