题解：P8426 [JOI Open 2022] 放学路 / School Road

· · 题解

本题或是广泛作为广义串并联图的练习题也好、或是具有着 m-n\le 13 的部分分也罢，几乎所有题解都在一开头均直接引导向广义串并联图的方向。本篇试图以正常的思路推导出解法。

最直观的想法是：建出 1 到 n 的最短路图（这是个 DAG），如果有某条边在 1 到 n 的某条简单路径上且两个方向都不在最短路图上，那么必然有解。设 d_u 是 u 到 n 的最短路，任取一条不在最短路图上的边 (u,v,w)，不妨 d_u\ge d_v，先从 1 沿着任意最短路走到 u，然后走这条边到 v，然后从 v 沿着任意最短路走到 n。因为路径上除了 (u,v) 这条边的 d 都是严格递减的，所以必然是简单路径。

P.S. 保留所有在 1 到 n 的某条简单路径上的点是容易的。一个方法是加一条边 (1,n) 然后取唯一包含 1,n 的点双。

然而这并不充分，因为我们可能“逆行”，即走某条边的反向边。显然只需要找有没有逆行一次的路径即可。下面称一个图合法当且仅当它的答案是 0，也就是无法找到这样逆行的路径。

下面直接把最短路图叫做 G，这是一个无权 DAG。

稍微画一下，感觉稍微复杂一点就能找到：如果所有边为 (1,2),(2,4),(1,3),(3,4),(2,3)，那么就能沿着 (2,3) 逆行。

由此猜测合法的充要条件为 G 是杏仁，然而不对，也可以是嵌套多层杏仁：

但凡有一条横跨的边就能找到。

所以正确的条件为：找不到当且仅当原图是一个 1 到 n 的杏仁，杏仁的每条边又可以扩展为一个杏仁……充分性十分显然，这样扩展出来的东西可以通过“杏仁图合法”为基础嵌套归纳证明能被扩展出的东西都合法。

必要性的说明可以把这个过程反过来，即我们可以通过不然将某个杏仁缩成边来将原图缩成一条边 (1,n)，这个显然和上面的等价。对于任意一个不合法的图，考虑尽量删边来保留任意一个极小的不合法但仍然保持“所有点都在 1 到 n 路径”这一条件的子图，那么这个子图必然缩到某一步的时候存在上述一条边横跨一个杏仁。

但是如何动态找到杏仁并删除呢？发现这个就相当于不断将由“出度和入度都为 1 的点”的链缩掉，如果两个点之间都被缩掉了那么它们间在原图就必然是一个“杏仁套杏仁套杏仁套杏仁……”的结构。实现的时候，不断找“出度和入度都为 1 的点 v”，删除入边 (u,v) 和出边 (v,w) 并加入边 (u,w) 即可，注意将边去重。

复杂度 \mathcal{O}(m\log m)。

回过头来看广为流传题解的做法，其实感觉非常非人类，就非要对着带权且无向的原图做呗。

#include<set>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<LL,int> PLI;
const int N=1e5+9,M=4e5+9;
int n,m;
int h[N],e[M],val[M],ne[M],idx=2;
bool on[N];
void add(int a,int b,int c){
    e[idx]=b,val[idx]=c,ne[idx]=h[a],h[a]=idx++;
    e[idx]=a,val[idx]=c,ne[idx]=h[b],h[b]=idx++;
}
set<int> ou[N],in[N];
int q[N],hh,tt;
void add(int a,int b){
    // printf("add %d %d\n",a,b);
    ou[a].insert(b),in[b].insert(a);
}
void chk(int i){
    if(in[i].size()==1&&ou[i].size()==1&&on[i]) on[i]=0,q[++tt]=i;
}
int dfn[N],low[N],timestamp;
int stk[N],top;
void tarjan(int u){
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;
    for(int i=h[u],v;i;i=ne[i]){
        if(!dfn[v=e[i]]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(low[v]==dfn[u]){
                int tmp=top;
                bool hv1=u==1,hvn=u==n;
                int y;
                do{
                    y=stk[top--];
                    hv1|=y==1,hvn|=y==n;
                }while(y^v);
                if(hv1&&hvn){
                    on[u]=1;
                    for(int i=top+1;i<=tmp;i++) on[stk[i]]=1;
                }
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
LL d[N]; bool vis[N];
void Dijkstra(){
    priority_queue<PLI,vector<PLI>,greater<PLI>> q;
    memset(d,0x3f,sizeof(d));
    q.push({d[1]=0,1});
    while(!q.empty()){
        PLI P=q.top(); q.pop();
        int u=P.se;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=h[u],v;i;i=ne[i]) if(v=e[i],val[i]&&on[v]&&d[u]+val[i]<d[v]) q.push({d[v]=d[u]+val[i],v});
    }
}
int main(){
    // freopen(".in","r",stdin);
    scanf("%d%d",&n,&m);
    add(1,n,0);
    for(int i=1,a,b,c;i<=m;i++) scanf("%d%d%d",&a,&b,&c),add(a,b,c);
    tarjan(1);
    // printf("on: "); for(int i=1;i<=n;i++) printf("%d",on[i]); puts("");
    Dijkstra();
    hh=0,tt=-1;
    for(int i=4;i<idx;i+=2){
        int a=e[i|1],b=e[i];
        if(on[a]&&on[b]){
            if(d[a]>d[b]) swap(a,b);
            // printf("%d %d %lld %d %lld\n",a,b,d[a],val[i],d[b]);
            if(d[a]+val[i]==d[b]) add(a,b); 
            else return puts("1"),0;
        }
    }
    for(int i=1;i<=n;i++) chk(i);
    while(hh<=tt){
        int u=q[hh++];
        int x=*in[u].begin(),y=*ou[u].begin();
        ou[x].erase(u),in[y].erase(u);
        add(x,y);
        for(int i:{x,y}) chk(i);
    }
    for(int i=2;i<n;i++) if(on[i]) return puts("1"),0;
    puts("0");
    return 0;
}