题解：AT_codefestival_2016_final_g Zigzag MST

ctzm · 2025-12-19 18:15:48 · 题解

乱胡奇怪做法，过了，发现是黑，吓出心脏病，我应该不能独立切黑的吧？

看题解，每个我都看不懂，都不是我的做法。遂写题解。

图灵托梦告诉我，将题目描述的加边方式改为：

给定 x,y,z，对于每个 0 \le i，加边 (x+i,y+i,z+2i)，点仍然是模 n 意义下的。

这样原题的加边方式就可以拆成 x,y,z 和 x+1,y,z+1，然后分别按照上面加边方式即可。

考虑模拟 Kruscal 过程，对于每个加边描述，可以用一个优先队列逐步扩展 i。

如果某个描述 x,y,z 在取到 i 尝试连边时，发现两个点已经在此之前被其他边连通成同一个连通块过，不能连边，则可以证明这个描述所有更大的 i 都不能连边。

简要证明：每个描述对于某个 i 建的边都有一个后继 i+1，边权统一加 2，点编号统一加 1，相对关系不变，因此这个描述后面的所有更大的 i 在考虑时仍然会发现两点联通。

因此一旦不能连边就跳过，如果能连边就连来构建 MST。每个加边模式最多失效被跳过 1 次，成功的加边总共最多 n-1 次，因此复杂度为 O((n+m) \log (n+m))。

直接看代码就理解了。

#include<bits/stdc++.h>
using namespace std;
int n,m,fa[200020],cnt;
long long ans;
int gtf(int x){
    return fa[x]==x?x:fa[x]=gtf(fa[x]);
}
priority_queue<pair<int,pair<int,int> > > q;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        q.push({-z,{x,y}});
        q.push({-(z+1),{(x+1)%n,y}});
    }
    while(q.size()){
        int w=-q.top().first,u=q.top().second.first,v=q.top().second.second;
        q.pop();
        int fu=gtf(u),fv=gtf(v);
        if(fu!=fv){
            fa[fu]=fv;
            ans+=w;
            cnt++;
            if(cnt==n-1)break;
            q.push({-(w+2),{(u+1)%n,(v+1)%n}});
        }
    }
    assert(cnt==n-1);
    cout<<ans;

    return 0;
}