Flame 题解

· · 题解

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

可以注意到无解的情况存在且只存在于原图是一棵树的情况：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]); // 合并
            }
        }
    }
}