记录编号	386373	评测结果	AAAAAAAAAAAAAAAA
题目名称	[USACO Hol10] 臭气弹	最终得分	100
用户昵称	xyz117	是否通过	通过
代码语言	C++	运行时间	0.156 s
提交时间	2017-03-24 13:59:53	内存使用	1.05 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const string ss="dotp.";
int n,m,p,q;
int d[310];
double f[310][310],x[310],pro;
void swap(double &xx,double &yy)
{
    double t;
    t=xx;
    xx=yy;
    yy=t;
}
void gauss()
{
    double t;
    int im,num=1;
    for(int k=1;k<=n;k++,num++)
    {
        im=k;
        for(int i=k+1;i<=n;i++)
            if(fabs(f[i][k])>fabs(f[im][k]))
                im=i;
        if(im!=k)
            for(int i=k;i<=n+1;i++)
                swap(f[num][i],f[im][i]);    
        if(!f[num][k])
        {
            num--;
            continue;    
        }
        for(int i=num+1;i<=n;i++)
        {
            if(!f[num][k])
                continue;
            t=f[i][k]/f[num][k];
            for(int j=k;j<=n+1;j++)
                f[i][j]-=t*f[k][j]; 
        }   
    }
    num--;
    for(int i=n;i>=1;i--)      
    {
        for(int j=n;j>=i+1;j--)
            f[i][n+1]-=f[i][j]*x[j];
        x[i]=f[i][n+1]/f[i][i];    
    }  
}
int main()
{
    freopen((ss+"in").c_str(),"r",stdin);
    freopen((ss+"out").c_str(),"w",stdout);
    int a,b;
    scanf("%d%d%d%d",&n,&m,&p,&q);
    if(p>q)
        p=q;
    pro=(double)p/q;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        d[a]++;
        d[b]++;
        f[a][b]+=1.0;
        f[b][a]+=1.0;    
    }    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(d[j])
                f[i][j]/=d[j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j]*=pro-1;
    for(int i=1;i<=n;i++)
        f[i][i]+=1.0;
    f[1][n+1]=pro;
    gauss();
    for(int i=1;i<=n;i++)
        printf("%.9lf\n",x[i]);
}