自动搬运

查看原文

来自洛谷，原作者为

	Augen_stern Du bist der ausschließliche Stern in meinen Augen. ||Du bist mein Augenstern. || 珍爱生命，远离 jcer

搬运于2025-08-24 22:37:40，当前版本为作者最后更新于2022-02-24 23:59:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目的意思就是求在某个时间时，图中有效边可以构成至少一个简单环；

可以注意到无解的情况存在且只存在于原图是一棵树的情况：$m=n-1$。

暴力我们就抛开不论了，这里提几种有意思的做法：

$\mathcal{O}(m\log m)$ $100 pts$

不难发现可以用二分去枚举时间。

所以我们可以先对源点进行多起点求到全图所有点的最短路；

接下来我们有两种思路：

1. 根据图的定义，统计每一个联通块的边数和点数，根据树与环的定义来判断答案。

2. 用 Tarjan 来统计环，直接暴切！

在此再次感谢验题人 Erinyes 对本题的巨大贡献。

$\mathcal{O}(m)$ $100pts$

我们可以发现，上述做法中的 $m$ 有点过大，注意到 $k$ 较小，发现二分其实是多余的，我们可以直接模拟整个蔓延过程，用宽搜遍历实现，并在其中用类似于最短路算法一样不断更新遍历到的结点（提前预处理出最短路的话没必要但可行）；

接着用并查集，将每一个源点记作一个集合，当两不同集合相遇时则合并；

若不相同，则更新答案，取时间最小值，顺带一提，此时直接输出是错误的。

此时的并查集若只考虑使用路径压缩，那么时间复杂度会退化 $\mathcal{O}(m\log m)$，也是可以接受的；

更好的，若要考虑 $\mathcal{O}(m)$，则须使用按秩合并。

且对于此时的时间复杂度，接近于 $\mathcal{O}(m)$。（注意到，就遍历一张图的时间；由于并查集的时间复杂度为反阿克曼函数，所以也就是常数时间。）

通过上述做法，可以 AC。

为了追求极致的最优解，我们可以发现在某个时间点后，遍历到的点时间将超过答案；

所以我们可以用记忆化来优化，只要搜到答案后，如果当前起始点的时间不比答案小，那么程序运行结束；

当然这种优化的极限复杂度还是 $\mathcal{O}(m)$ 级别，但由于 $n$ 较小，特殊构造可以为 $k=1$ 且在一条链的一端，而构造一个完全图（甚至只有一个三元环）在另一端，但这样要么使 $m$ 和 $n$ 差不多大，要么使最后的答案变小。综上，这无法使优化退化，就当是一种玄学优化吧。

在此再次感谢验题人 jinqihao2023 和 leihonglongyin 对本题的巨大贡献。

代码如下：

并查集：

int find(int x){
	if(fa[x]==x) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
void merge(int a,int b){
	int x=find(a),y=find(b);
	if(x==y) return;
	if(rank[x]<=rank[y]) fa[x]=y,rank[y]=max(rank[y],rank[x]+1);
	else fa[y]=x,rank[x]=max(rank[x],rank[y]+1);
} // 按秩合并 路径压缩（其实只需要路径压缩就行了）
signed main() {
	for(int i=1;i<=n;i++) fa[i]=i,rank[i]=i;
}

宽搜：

signed main() {
	while(!q.empty()){
		int x=q.front(); q.pop();
		if(dis[x]>ans) break; // 记忆化
		for(int i=h[x];i;i=t[i].next){
			if(vst[i]) continue;
			int y=t[i].to;
			dis[y]=min(dis[y],dis[x]+1); // 更新时间
			vst[i]=vst[i^1]=1; // 不走回路
			if(!c[y]) c[y]=c[x], q.push(y); // 蔓延
			else{
				if(find(c[x])==find(c[y])) ans=min(ans,dis[y]);
				else merge(c[x],c[y]); // 合并
			}
		}
	}
}