自动搬运

查看原文

来自洛谷，原作者为

	ケロシ Blue Archive

搬运于2025-08-24 23:11:15，当前版本为作者最后更新于2025-03-19 18:28:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

首先注意到转移肯定是：

初始 $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]);
}