bzoj3270博物馆——期望概率DP

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3270

设计一个状态表示两个人分别在两个点的状态，带个标号num[i][j]；

据此得到状态之间转移的关系所构成的n元方程，高斯消元求解；

要注意起点的概率要+1，而且开始时两个人在两个点是有区分的，所以不能(A,B)和(B,A)都加；

用scanf会CE，所以改成了快读和cin；

调了一天的才找到错误竟然是把d数组和deg数组弄混了！

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,A,B,deg[25],ct,head[25],cnt;
double d[630],a[630][630],p[25];
struct N{
    int to,next;
    N(int t=0,int n=0):to(t),next(n) {}
}edge[625];
int num(int a,int b){return n*(a-1)+b;}
void gauss()
{
    for(int x=1;x<=cnt;x++)
    {
        int nw=x;
        for(int y=x+1;y<=cnt;y++)
            if(fabs(a[y][x])>fabs(a[nw][x]))nw=y;
        if(nw!=x)
            for(int k=x;k<=cnt+1;k++)swap(a[nw][k],a[x][k]);
        for(int y=x+1;y<=cnt;y++)
        {
            double r=a[y][x]/a[x][x];
            for(int t=cnt+1;t>=x;t--)//
                a[y][t]-=r*a[x][t];
        }
    }
    for(int i=cnt;i;i--)
    {
        for(int j=i+1;j<=cnt;j++)
            a[i][cnt+1]-=a[i][j]*d[j];
        d[i]=a[i][cnt+1]/a[i][i];
    }
}
int rd()
{
    char ch=getchar();int x=0,f=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int main()
{
//    scanf("%d%d%d%d",&n,&m,&A,&B);
    n=rd();m=rd();A=rd();B=rd();
    for(int i=1,x,y;i<=m;i++)
    {
//        scanf("%d%d",&x,&y);
        x=rd();y=rd();
        deg[x]++,deg[y]++;
        edge[++ct]=N(y,head[x]);head[x]=ct;
        if(x==y)continue;
        edge[++ct]=N(x,head[y]);head[y]=ct;
    }    
    for(int i=1;i<=n;i++)
//        scanf("%lf",&p[i]);
        cin>>p[i];
    cnt=n*n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)    if(i!=j)
        {
            int x=num(i,j);
            for(int k=head[i];k;k=edge[k].next)
            {
                for(int l=head[j];l;l=edge[l].next)
                {
                    a[num(edge[k].to,edge[l].to)][x]+=(1.0-p[i])*(1.0-p[j])/deg[i]/deg[j];
//                    a[num(i,edge[l].to)][x]+=(1.0-p[j])*p[i]/d[j];//重复 
                }
                a[num(edge[k].to,j)][x]+=(1.0-p[i])*p[j]/deg[i];
            }
            for(int l=head[j];l;l=edge[l].next)a[num(i,edge[l].to)][x]+=(1.0-p[j])*p[i]/deg[j];
            a[x][x]+=p[i]*p[j];
        }
    for(int i=1;i<=cnt;i++)a[i][i]-=1.0;
    a[num(A,B)][cnt+1]-=1.0;
//    printf("a[%d]=%.2lf
",num(A,B),a[num(A,B)][cnt+1]);
//    a[num(B,A)][cnt+1]-=1.0;//两人有区分！ 
    gauss();
    for(int i=1;i<=n;i++)
        printf("%.6lf ",d[num(i,i)]);
    return 0;
}