专栏文章

题解：P3436 [POI 2006] PRO-Professor Szu

ccjrqwq
P3436题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minvk7mz
此快照首次捕获于
2025/12/02 09:03
3 个月前
此快照最后确认于
2025/12/02 09:03
3 个月前
查看原文
用 Kosaraju 的同志里边请。
也没人告诉我 Kosaraju 求图的部分点的强连通分量要加额外判断呀？？？
讲述我悲惨的调题经历。
首先，看到求 1∼n1\sim n 到 n+1n+1，对于某点 ii 要到 n+1n+1，那把路径上的边全部反过来，就是从 n+1n+1 到 1∼n1\sim n，所以我们反着建图。这样，我们知道了起点，就比较好做。
如果路径可以经过一个环（自环也行），那么可以无限套娃，不停转圈，方案数有无穷个。这时候想到对有向图缩点。如果某个强连通分量之中存在边，也可以说是存在两个点或存在自环，那么就有无穷个方案。如果该强连通分量只有一个点呢？那由他的前驱来转移，这是基础的缩点后在 DAG 上 DP。
以上就是本题的思路。
如果你和我一样使用 Kosaraju，并且第一次搜索只从 n+1n+1 开始，那么会出现一些问题。回顾算法的流程，我们发现第一次搜索，记录了每个节点 ii 的离开时间 lil_i。如果两个节点 x,yx,y 不在同一个 SCC，且 lx>lyl_x > l_y，那么 yy 不可达 xx。如果 yy 可达 xx，只可能是 x,yx,y 同属于一个 SCC，或者 ly>lxl_y > l_x。
然后到第二次搜索，此时我们保证不会把其他 SCC 错误地访问的原因，是因为在缩点后的 DAG 中，该 SCC 的前驱已经被访问过了，该 SCC 的后继由于边被倒过来了，所以访问不到，而同一个 SCC 中边被倒过来是不会变动的。
但是，我们如果只 DFS 了一次，并不能保证某个 SCC 的所有前驱都被访问到了，n+1n+1 不一定可到达某个前驱，所以就不对，比如下图。
这里是图片解释。当 n=2n=2 时，蓝色边为原图，绿色边为取反后的图，33 只会到达 11。访问到 11 时，发现可以到达 22，并且 22 还没被访问过，于是 1,21,2 被放入同一个 SCC，于是就错了。解决的方法有两个：
  1. 用一个数组记录 n+1n+1 可达的点，把不可达的点全部忽略。
  2. 先缩点全图，然后把入度为 00 的点都删去，但是保留 n+1n+1。
本题还有一些其他的细节，可以看其他题解，有比较好的实现方法。
希望能增加屏幕前的你对 Kosaraju 的理解，这里提供一份实现。
CPP
#include<bits/stdc++.h>
using namespace std;
constexpr int N =1e6+10;
int n,m;
vector<int>e[N],re[N],ne[N];
int cir[N];

int vis[N],stk[N],c,scc[N];
void dfs(int u) {
	vis[u] = 1;
	for (int v : e[u]) {
		if (!vis[v]) dfs(v);
	}
	stk[++c] = u;
}
int tag;
void rdfs(int u) {
	scc[u] = tag;
	for (int v : re[u]) {
		if (!scc[v] && vis[v]) rdfs(v);
	}
}

int scccir[N],in[N],f[N];
int main() {
	cin.tie(nullptr) -> sync_with_stdio(false);
	cin>>n>>m;
	for (int i=1;i<=m;i++) {
		int x,y; cin>>x>>y;
		if (x == y) {
			cir[x] = 1;
		}
		else {
			e[y].push_back(x);
			re[x].push_back(y);
		}
	}
	dfs(n+1);
	for (int i=c;i;i--) {
		if (!scc[stk[i]] && vis[stk[i]]) tag++,rdfs(stk[i]);
	}
	for (int i=1;i<=n+1;i++) {
		if (scc[i] == 0) continue;
		if (cir[i]) scccir[scc[i]] = 1;
		for (int v : e[i]) {
			if (scc[v] == 0) continue;
			if (scc[i] == scc[v]) scccir[scc[i]] = 1;
			else {
				ne[scc[i]].push_back(scc[v]);
				in[scc[v]]++;
			}
		}
	}
	queue<int>q;
	q.push(scc[n+1]);
	f[scc[n+1]] = 1;
	while(!q.empty()) {
		int u = q.front(); q.pop();
		if (scccir[u] == 1) f[u] = 36501;
		for (int v : ne[u]) {
			
			f[v] = min(f[v] + f[u], 36501);
			in[v] --;
			if (in[v] == 0) q.push(v);
		}
	}
	int mx = 0;
	vector<int>ans;
	for (int i=1;i<=n;i++) {
		if (scc[i] == 0) continue;
		if (f[scc[i]] > mx) mx = f[scc[i]], ans.clear();
		if (f[scc[i]] == mx) ans.push_back(i);
	}
	if (mx == 36501) {
		cout << "zawsze\n";
	}
	else {
		cout << mx << '\n';
	}
	cout << ans.size() << '\n';
	for (int x : ans) cout << x << ' ';
	return 0;
}
谨以此篇题解记录我逝去的一个夜晚和下午。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...