题解 P6030 [SDOI2012]走迷宫

· · 题解

题面传送门

之所以写个题解是因为题解区大部分题解的做法都有 bug（u1s1 周六上午在讨论区里连发两个 hack 的是我，由于我被禁言才让 ycx 代发的）

首先碰到这种期望题，我们套路地设 dp_u 为从节点 u 走到节点 n 经过的节点数的期望值，那么显然有转移方程 dp_u=\dfrac{1}{deg_u}(\sum\limits_{(u,v)\in E}dp_v)+1，由于这个 dp 方程存在环，故需按照 P3232 游走 的套路进行高斯消元，具体来说你将这 n 个 dp 转移式写成矩阵的形式高斯消元一下即可。

等等……10^4 你让我跑高斯消元？

注意到题目中有个条件，就是每个强连通分量大小 \le 100，因此考虑先将原图进行一遍 SCC 缩点，缩点完成后显然原图变成了一个 DAG，我们考虑按这个 DAG 的拓扑序倒序（或者说，以 t 为起点拓扑排序）对每个强连通分量中的点计算一遍 dp 值，具体来说我们给当前强连通分量中的所有点重新编号，对于形如 dp_u=\dfrac{1}{deg_u}(\sum\limits_{(u,v)\in E}dp_v)+1 的式子，如果 v 与 u 在同一个强连通分量中那就按照套路将式子改写成一个 dp_u 与这样的 dp_v 的关系式，否则由于我们按照拓扑序倒序计算答案，dp_v 的值肯定已经计算好了，那么我们把它当作常数项拖到右边去即可。具体实现的时候可以以 s 为起点跑一遍 tarjan，因为最终强连通分量的编号本身就是按拓扑序倒序编好号的了，就 duck 不必再写遍拓扑排序了，直接从 1 枚举到 \text{强连通分量个数} 依次计算即可。

记 s_i 为强连通分量大小，那么该算法复杂度 T(n)=\sum\limits_{i=1}^ms_i^3，而 s_i\le 100，故 T(n)\le\dfrac{10^4}{100}\times 100^3=10^8，可以通过此题。

那么什么情况输出 INF 呢？显然如果 s 不能到 t 答案肯定是 INF，接下来就是我要强调的地方了，不少题解都认为，只要存在 s 能到达但却不能到达 t 的点就 INF，但考虑下面的数据：

3 2 1 3
1 3
3 2

事实上，2 虽然能够从 3 到达，但从 1\to 2 的路径上已经经过 3 了，因此是可以到达 2 的，答案应当为 1.000。

还有的题解稍微明智些，把不能到达的点的 dp 值设为 \infty，然后判是否有 dp_s=\infty，这样做是可以避免掉上述情况的，但由于实现上出了个小 bug（如果一个点出度为 0 那么它的 dp 值就是 \infty），导致其可以被以下的数据叉掉：

5 5 1 5
1 5
1 2
2 3
3 4
4 2

我的做法是，先建反图，以 t 为起点做一遍 DFS 找出所有能到达 t 的点，然后如果一个点不能到达 t 那就令它的 dp 值为 \infty，这样又可避免上述情况。

当然我的做法可能也存在漏洞（只是我发现不了了），如果发现漏洞请及时提出，谢谢。

我认为做题还是要严谨些，愿管理员把 hack 数据加入本题的测试数据中。

那问题就来了，为什么我就不能把我 hack 的这份热情放到 CF 比赛中呢

const int MAXS=100;
const int MAXN=10000;
const int MAXM=1e6;
const double INF=1e15;
int n,m,s,t;
int hd[MAXN+5],to[MAXM*2+5],nxt[MAXM*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int bel[MAXN+5],cmp=0,dfn[MAXN+5],low[MAXN+5],tim=0;
bool vis[MAXN+5];int stk[MAXN+5],top=0;vector<int> scc[MAXN+5];
vector<int> rev[MAXN+5];bool can[MAXN+5];
void dfs(int x){
    if(can[x]) return;can[x]=1;
    for(int y:rev[x]) dfs(y);
}
void tarjan(int x){
    dfn[x]=low[x]=++tim;vis[x]=1;stk[++top]=x;
    for(int e=hd[x];e;e=nxt[e]){
        int y=to[e];
        if(!dfn[y]) tarjan(y),chkmin(low[x],low[y]);
        else if(vis[y]) chkmin(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]){
        cmp++;int o;
        do {
            o=stk[top--];vis[o]=0;
            scc[bel[o]=cmp].pb(o);
        } while(o!=x);
    }
}
int id[MAXN+5],seq[MAXS+5],subsiz=0,deg[MAXN+5];
double dp[MAXN+5],a[MAXS+5][MAXS+5],f[MAXS+5];
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);deg[u]++;
        adde(u,v);rev[v].pb(u);
    }
    tarjan(s);dfs(t);if(!dfn[t]) return puts("INF"),0;
    for(int i=1;i<=cmp;i++){
        subsiz=0;memset(a,0,sizeof(a));memset(f,0,sizeof(f));
        for(int u:scc[i]){seq[++subsiz]=u;id[u]=subsiz;}
        for(int u:scc[i]){
            int p=id[u];
            if(u==t){a[p][p]=1;continue;}
            a[p][p]=a[p][subsiz+1]=deg[u];
            for(int e=hd[u];e;e=nxt[e]){
                int v=to[e];
                if(bel[v]==bel[u]) a[p][id[v]]--;
                else a[p][subsiz+1]+=dp[v];
            }
            if(!can[u]) a[p][subsiz+1]=INF;
        }
//      for(int j=1;j<=subsiz;j++) for(int k=1;k<=subsiz+1;k++)
//          printf("%.3lf%c",a[j][k],(k==subsiz+1)?'\n':' ');
        for(int j=1;j<=subsiz;j++){
            int t=j;
            for(int k=j+1;k<=subsiz;k++) if(fabs(a[k][j])>fabs(a[t][j])) t=k;
            for(int k=j;k<=subsiz+1;k++) swap(a[t][k],a[j][k]);
            for(int k=j+1;k<=subsiz+1;k++) a[j][k]/=a[j][j];a[j][j]=1;
            for(int k=j+1;k<=subsiz;k++){
                for(int l=j+1;l<=subsiz+1;l++) a[k][l]-=a[k][j]*a[j][l];
                a[k][j]=0;
            }
        }
        for(int j=subsiz;j;j--){
            f[j]=a[j][subsiz+1];
            for(int k=j+1;k<=subsiz;k++) f[j]-=f[k]*a[j][k];
//          printf("%.3lf\n",f[j]);
        }
        for(int j=1;j<=subsiz;j++){
            if(f[j]>1e9) dp[seq[j]]=INF;
            else dp[seq[j]]=f[j];
        }
    }
//  for(int i=1;i<=n;i++) cout<<dp[i]<<endl;
    if(dp[s]>1e9) puts("INF");
    else printf("%.3lf\n",dp[s]);
    return 0;
}