hdu-4418-Time travel-高斯+概率dp

把N个点先转化为2*N-2个点。

比方说把012345转化成0123454321。

这样，就能够找出随意两两个点之间的关系。

然后依据关系能够得出来一个一元多项式的矩阵。

然后就用高斯消元求出矩阵就可以。

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

#include<queue>

#include<math.h>

using namespace std;

#define eps 1e-6

#define zero(x) ((fabs(x)<eps?0:x))

#define maxn 220

double a[maxn][maxn];

int g[maxn],cnt;

int n,m,st,ed;

double p[maxn];

int guss(int n)

{

    int r;

    for(int i=0;i<n;i++)

    {

        r=i;

        for(int j=i+1;j<n;j++)

        {

            if(fabs(a[j][i])>fabs(a[r][i]))r=j;

        }

        if(!zero(a[r][i]))return 0;

        if(r!=i){

                for(int j=0;j<=n;j++)

                    swap(a[i][j],a[r][j]);

        }

        for(int j=i+1;j<=n;j++)a[i][j]/=a[i][i];

        a[i][i]=1.0;

        for(int j=0;j<n;j++)

        {

            if(j==i)continue;

            for(int k=i+1;k<=n;k++)

            {

                a[j][k]-=a[i][k]*a[j][i];

            }

            a[j][i]=0;

        }

    }

    return 1;

}

void bfs()

{

    queue<int>que;

    while(!que.empty())que.pop();

    que.push(st);

    memset(g,-1,sizeof(g));

    cnt=0;

    g[st]=cnt++;

    while(!que.empty())

    {

        int x=que.front();

        que.pop();

        for(int i=1;i<=m;i++)

        {

            if(!zero(p[i]))continue;

            int y=(i+x)%n;

            if(g[y]==-1)

            {

                g[y]=cnt++;

                que.push(y);

            }

        }

    }

}

int main()

{

    int T,d;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d%d%d%d",&n,&m,&ed,&st,&d);

        for(int i=1;i<=m;i++)

        {

            scanf("%lf",&p[i]);

            p[i]=1.0*p[i]/100.0;

        }

        if(ed==st)

        {

            puts("0.00");

            continue;

        }

        n=2*n-2;

        if(d==1)st=n-st;

        bfs();

        if(g[ed]==-1&&g[n-ed]==-1){

                puts("Impossible !");

                continue;

        }

        memset(a,0,sizeof(a));

        for(int i=0;i<n;i++)

        {

            if(g[i]==-1)continue;

            if(i==ed||i==n-ed)

            {

                a[g[i]][g[i]]=1;

                a[g[i]][cnt]=0;

                continue;

            }

            a[g[i]][g[i]]=1.0;

            for(int j=1;j<=m;j++)

            {

                int y=(i+j)%n;

                if(g[y]==-1)continue;

                a[g[i]][g[y]]-=p[j];

                a[g[i]][cnt]+=1.0*j*p[j];

            }

        }

        if(!guss(cnt))puts("Impossible !");

        else printf("%.2lf\n",a[g[st]][cnt]);

    }

    return 0;

}