比赛 |
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;
}