挑战最唐最神经做法！！1

· · 题解

哥们来写唐诗做法了！！1111

首先注意到转移肯定是：

f_u=\min(\min f_v+1,\max f_v)

初始 f_{ed}=0，终点走反边不可达的点为无穷大，那么答案就是满足方程的最小的 f_{st}。

这里有一种优质做法，就是先把所有的值设为 0，然后不断跑转移方程使得某个点暂时满足方程，迭代 O(n) 次后所有方程都满足，直接输出即可，复杂度 O(nm)。

但是本人太菜了，不会这一种做法，于是想出了一种唐诗做法。

考虑先跑一次 bfs，跑出转移的前半部分 f_u=\min f_v+1。

接下来考虑 \max f_v 的限制可能会形成一个类似环状的东西，这样就可以集体 f_u 减一（参考样例三）。

接下来考虑具体什么时候可以集体减一，不难发现若 f_u \le \max f_v 且 f_u=f_v，那么点 v 就支配了点 u，那么点 u 就向点 v 连一条边。

那么不难发现，将图的强连通分量缩掉之后，若一个点没有出边，也就是没有被支配，那么就可以集体减一了。

接下来重复这个过程即可，每次跑 bfs，然后找能集体减一的块。

接下来口胡一下复杂度，注意到每次集体减一的块的 f_u 都是路径上最大的，且每次减一后块的大小会增大，所以只会迭代 O(n) 次。

时间复杂度 O(nm)。

const int N = 3e3 + 5;
const int M = 1e5 + 5;
const int INF = 1e9 + 7;
int n, m, st, ed;
vector<int> e[N], g[N];
int f[N], vis[N];
int fi[N], ne[M], to[M], ecnt;
int dfn[N], low[N], cnt;
int stk[N], tp;
int scc[N], sc;
int ru[N], b[N];
void add(int u, int v) {
    ne[++ ecnt] = fi[u];
    to[ecnt] = v;
    fi[u] = ecnt;
}
void bfs() {
    FOR(i, 1, n) vis[i] = 0;
    deque<int> q;
    q.push_back(ed);
    while(! q.empty()) {
        int u = q.front();
        q.pop_front();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int v : e[u]) {
            if(f[v] == f[u]) {
                q.push_front(v);
            }
            if(f[v] >= f[u] + 1) {
                f[v] = f[u] + 1;
                q.push_back(v);
            }
        }
    }
}
void clear() {
    FOR(i, 1, n) fi[i] = dfn[i] = low[i] = vis[i] = 0;
    ecnt = cnt = sc = tp = 0;
}
void tarjan(int u) {
    dfn[u] = low[u] = ++ cnt;
    stk[++ tp] = u;
    vis[u] = 1;
    for(int i = fi[u]; i; i = ne[i]) {
        int v = to[i];
        if(! dfn[v]) {
            tarjan(v);
            chmin(low[u], low[v]);
        }
        else if(vis[v]) {
            chmin(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]) {
        sc ++;
        while(1) {
            scc[stk[tp]] = sc;
            vis[stk[tp]] = 0;
            tp --;
            if(stk[tp + 1] == u) break;
        }
    }
}
void solve() {
    cin >> n >> m;
    REP(_, m) {
        int u, v;
        cin >> u >> v;
        e[v].push_back(u);
        g[u].push_back(v);
    }
    cin >> st >> ed;
    FOR(i, 1, n) f[i] = INF;
    f[ed] = 0;
    while(1) {
        bfs();
        clear();
        FOR(u, 1, n) {
            int mx = 0; b[u] = 0;
            for(int v : g[u]) chmax(mx, f[v]);
            if(mx <= f[u]) {
                for(int v : g[u]) 
                    if(f[v] == f[u]) add(u, v);
            }
            else {
                b[u] = 1;
            }
        }
        bool ok = 0;
        FOR(u, 1, n) if(! dfn[u]) tarjan(u);
        FOR(i, 1, sc) ru[i] = 0;
        FOR(u, 1, n) for(int i = fi[u]; i; i = ne[i]) {
            int v = to[i];
            if(scc[u] != scc[v]) ru[scc[u]] ++;
        }
        FOR(u, 1, n) if(f[u] != INF && scc[u] != scc[ed] && ! ru[scc[u]] && ! b[u]) f[u] --, ok = 1;
        if(! ok) break;
    }
    cout << (f[st] == INF ? - 1 : f[st]);
}