题解 P6030 【[SDOI2012]走迷宫】

· · 题解

可以考虑使用概率dp方法求出答案，然后就想到了直接dfs，最后就有了40，前提是INF判断的没有问题。

根据数据范围的提示发现记忆化搜索不可行的原因在于转移有环，对于有环的转移常用的办法是高斯消元，然后这样就有了60分，原因在于时间复杂度过高。

所以没法做了？观察数据得到搜索转移不了的环的大小最大是100，可以承受n^3的高斯消元，于是可以对于每个环跑高斯消元，别的直接搜索即可。

这道题完了？然而并不是，还需要注意INF的判断，这其实挺恶心的，不过一句话概括就是如果有一个点能够被出发点走到但是走不到终点，那么答案即为INF。

但是不得不承认代码还是很难写的。。。慢慢调吧。


#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10;
vector<int> E[N];
int s,t,d[N];
int stk[N],tp,Time,low[N],dfn[N],col[N],cnt;
vector<int> dcc[N],G1[N],G2[N];
void tarjan(int u){
    dfn[u]=low[u]=++Time;
    stk[++tp]=u;
    for(int i=0;i<E[u].size();i++){
        int v=E[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(!col[v])low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        cnt++;
        while(1){
            int x=stk[tp--];
            dcc[cnt].push_back(x);
            col[x]=cnt;
            if(x==u)break;
        }
    }
}
int rd[N],num[N],que[N],rk[N],hh,tt;
double a[220][220],b[220],f[N];
int g[N];
struct Edge{
    int to,nxt,tag;
}e[N*100];
int h[N],idx;
void Ins(int a,int b,int c){
    e[++idx].to=b;e[idx].nxt=h[a];
    e[idx].tag=c;h[a]=idx;
}
void dfs(int u){
    if(g[u])return;
    for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!g[v]&&!e[i].tag)
            dfs(v);
        if(g[v]==0&&v!=col[t]){
            puts("INF");
            exit(0);
        }
    }
    if(h[u]&&u!=col[t])g[u]=1;
}
void calc(int k){
    int n=dcc[k].size();
    for(int i=1;i<=n;i++){
        num[i]=dcc[k][i-1];
        rk[dcc[k][i-1]]=i;
    }
    for(int i=1;i<=n;i++){
        b[i]=0;
        for(int j=1;j<=n;j++)
            a[i][j]=0;
    }
    for(int i=1;i<=n;i++){
        a[i][i]=1;
        if(num[i]^t){
            b[i]=1;
            for(int j=0;j<E[num[i]].size();j++){
                int v=E[num[i]][j];
                if(f[v]||v==t)b[i]+=f[v]/d[num[i]];
                else a[i][rk[v]]-=1.0/d[num[i]];
            }
        }
    }
    for(int i=1;i<=n;i++){
        int p=i;
        for(int j=i;j<=n;j++)
            if(fabs(a[j][i])>fabs(a[p][i]))p=j;
        swap(a[p],a[i]);swap(b[p],b[i]);
        for(int j=1;j<=n;j++){
            if(i^j){
                double r=a[j][i]/a[i][i];
                for(int k=i;k<=n;k++)
                    a[j][k]-=a[i][k]*r;
                b[j]-=b[i]*r;
            }
        }
    }
    for(int i=1;i<=n;i++)
        f[num[i]]=b[i]/a[i][i];
}
int main(){
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    int n,m;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        E[a].push_back(b);
        d[a]++;
    }
    tarjan(s);
    if(!dfn[t]){
        puts("INF");
        return 0;
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<E[i].size();j++){
            int v=E[i][j];
            if(col[v]^col[i]){
                Ins(col[i],col[v],v==t);
                G2[col[v]].push_back(col[i]),rd[col[i]]++;
            }
        }
    dfs(col[s]);
    que[hh]=col[t];
    while(hh<=tt){
        int u=que[hh++];
        calc(u);
        for(int i=0;i<G2[u].size();i++){
            int v=G2[u][i];
            rd[v]--;
            if(!rd[v])que[++tt]=v;
        }
    }
    printf("%.3lf\n",f[s]);
    return 0;
}