BZOJ1778: [Usaco2010 Hol]Dotp 驱逐猪猡

给出n个节点m条边无向图，炸弹从1开始走，有p/q的概率爆炸，否则等概率移到别的点
求在每个点爆炸概率
f[i,j]-第j秒到点i的概率 W=p/q 则f[i,j]=sigma(1-W)/D[i]*f[k,j-1]
其中D[i]为点i的度，k与i有连边
Ans(i)=W(f[i,0]+f[i,1]+f[i,2]+……)
=Wf[i,0]+W(1-W)/D[i](sigma f[k,0]+sigma f[k,1]+sigma f[k,2]……)
=Wf[i,0]+sigma (1-W)/D[i]*Ans(k)，高斯消元解即可。
以上为典型的错误！！系数写错，把D[i]改成D[k]即可。

第一次写，很顺；第二次，系数配错，高斯消元写错，WA两发。

很好。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
//#include<iostream>
using namespace std;

const double eps=1e-13;
int n,m;
#define maxn 311
#define maxm 100011
struct Edge{int to,next;};
struct Graph
{
    Edge edge[maxm];
    int first[maxn],le,du[maxn];
    Graph()
    {
        memset(first,0,sizeof(first));le=2;
        memset(du,0,sizeof(du));
    }
    void in(int x,int y)
    {
        edge[le].to=y;
        edge[le].next=first[x];
        first[x]=le++;
    }
    void insert(int x,int y)
    {
        in(x,y);
        in(y,x);
        du[x]++;du[y]++;
    }
}g;
double mat[maxn][maxn];
int x,y;double w;
void gauss()
{
    for (int i=1;i<=n;i++)
    {
        int r=i;
        for (int j=i+1;j<=n;j++) if (mat[j][i]>mat[r][i]) r=j;
        for (int j=i;j<=n+1;j++) {double t=mat[r][j];mat[r][j]=mat[i][j];mat[i][j]=t;}
        for (int j=i+1;j<=n;j++)
            for (int k=n+1;k>=i;k--)
                mat[j][k]-=mat[j][i]/mat[i][i]*mat[i][k];
    }
    for (int i=n;i>=1;i--)
    {
        for (int j=n;j>i;j--) mat[i][n+1]-=mat[j][n+1]*mat[i][j];
        mat[i][n+1]/=mat[i][i];
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&x,&y);
    if (x>y) x=y;w=(double)x/y;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        g.insert(x,y);
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n+1;j++) mat[i][j]=0.0;
        for (int j=g.first[i];j;j=g.edge[j].next)
        {
            Edge &e=g.edge[j];
            mat[i][e.to]+=(w-1)/g.du[e.to];
        }
        mat[i][i]=1.0;
    }
    mat[1][n+1]=w;
    gauss();
    for (int i=1;i<=n;i++) printf("%.9f
",mat[i][n+1]);
    return 0;
}