#1T2最小生成树改错

VOID_DxC · 2025-08-02 18:32:55 · 个人记录

啊啊啊啊啊啊

题目传送门

思路赛时就胡出来了，先构造最小生成树。对于每一次查询，答案就是两个节点在最小生成树上的链中最长边的权值。

权值的查找正解是在倍增跳lca的过程中更新，我先尝试树剖没剖出来，又去学了倍增，在120多行的诗山代码中出现了没建双向边和log值访问越界的问题，在老师的帮助下调傻了

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e6+5;
const int L=20;
int fa[N];
int up[L][N],maxn[L][N];
int dep[N];
//最开始记录边的结构体 
struct node{
    int x,y,w;
}e[N],q[N];
//链式前向星结构体 
struct edge{
    int to,nxt,v;
}chk[N];
//最小生成树的并查集 
bool cmp(node a,node b){
    return a.w<b.w;
}
int findF(int x){
    if(x==fa[x]) return x;
    fa[x]=findF(fa[x]);
    return fa[x];
}

int head[N];
int n,m,u,v,w,cnt,sum,ant;
//最小生成树的加边函数 
void add(int x,int y,int w){
    chk[++ant].to=y;
    chk[ant].nxt=head[x];
    chk[ant].v=w;
    head[x]=ant;
}
//倍增预处理 
void dfs(int u,int ff,int elen){
//  cout<<u<<':';
    up[0][u]=ff;
    maxn[0][u]=elen;
    dep[u]=dep[ff]+1;
    for(int i=head[u];i;i=chk[i].nxt){
        int dd=chk[i].to;
//      cout<<dd<<' '; 
        if(dd==ff) continue;
        dfs(dd,u,chk[i].v);
    }
//  cout<<'\n';
}
//预处理 
void pp(int n,int root){
    dep[root] = -1;
    dfs(root,root,0);
    for(int k=1;k<L;k++){
        for(int x=1;x<=n;x++){
            up[k][x]=up[k-1][up[k-1][x]];
            maxn[k][x]=max(maxn[k-1][x],maxn[k-1][up[k-1][x]]);
        } 
    }
}
//求长度 
int getedge(int u,int v){
    int res=0;
    if(dep[u]<dep[v]){
        swap(u,v);
    } 
    for(int k=L-1;k>=0;k--){
        if(dep[up[k][u]]>=dep[v]){
            res=max(res,maxn[k][u]);
            u=up[k][u];
        }
    }
    if(u==v) return res;
    for(int k=L-1;k>=0;k--){
        if(up[k][u]!=up[k][v]){
            res=max(res,maxn[k][u]);
            res=max(res,maxn[k][v]);
            u=up[k][u];
            v=up[k][v];
        }
    }
    res=max(res,maxn[0][u]);
    res=max(res,maxn[0][v]);
//  cout<<up[0][u]<<'\n';
    return res;
}
int main(){
     freopen("mst.in","r",stdin);
     freopen("mst.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        cin >> u >> v >>w;
        e[++cnt].x=u;e[cnt].y=v;e[cnt].w=w;
        e[++cnt].x=v;e[cnt].y=u;e[cnt].w=w;
    }
    //复制一份查找用 
    for(int i=1;i<=cnt;i++){
        q[i].w=e[i].w;q[i].x=e[i].x;q[i].y=e[i].y;
    }
    sort(e+1,e+cnt+1,cmp);
    int k=0,tot=0;
    for(int i=1;i<=cnt;i++){
        if(findF(e[i].x)!=findF(e[i].y)){
            tot+=e[i].w;
            fa[findF(e[i].x)]=e[i].y;
            add(e[i].x,e[i].y,e[i].w);//建立最小生成树 
            add(e[i].y,e[i].x,e[i].w);
            k++;
            if(k==n-1) break;
        }
    }
    pp(n,1);
    //查找 
    for(int i=1;i<=cnt;i+=2){
        int xx=q[i].x;
        int yy=q[i].y;
        cout << getedge(xx,yy) << '\n';
    }
    return 0;
}