动态最小生成树

做法

• 先把原始边存起来方便修改
• 需要查询只用编号在[l,r]范围内的边时，再把这些边提取出来跑最小生成树即可

代码

// Problem: 动态最小生成树
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9986/H
// Memory Limit: 1048576 MB
// Time Limit: 10000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=3e4+5;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int n,m,q,fa[N],depth[N];
struct edge{
    int u,v,w;
}e[N],ee[N];

bool cmp(edge x,edge y){
    return x.w<y.w;
}

void init(int n){
    for(int i=1;i<=n;i++) 
        fa[i]=i,depth[i]=1;
}
//查询树的根
int find(int x){
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
//合并a和b所属的集合   
void unite(int a,int b){
    a=find(a),b=find(b);
    if(depth[a]==depth[b]){
        depth[a]=depth[a]+1;
        fa[b]=a;
    }
    else{
        if(depth[a]<depth[b]) fa[a]=b;
        else fa[b]=a;
    }
}
//判断a和b是否属于同一个集合
bool same(int a,int b){
    return find(a)==find(b);
}

ll Kruskal(int len){
    ll res=0;int count=0;
    for(int i=0;i<len;i++){
        if(!same(ee[i].u,ee[i].v)){
            unite(ee[i].u,ee[i].v);
            res+=ee[i].w;
            count++;
        }
        if(count==n-1) return res;
    }
    return -1;
}

void solve(){
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }

    while(q--){
        int op;cin>>op;
        if(op==1){
            int x,y,z,t;cin>>x>>y>>z>>t;
            e[x]={y,z,t};
        }
        else if(op==2){
            int l,r;cin>>l>>r;
            rep(i,l,r) ee[i-l]=e[i];
            init(n);
            sort(ee,ee+r-l+1,cmp);
            ll k=Kruskal(r-l+1);
            if(k!=-1) cout<<k<<"\n";
            else cout<<"Impossible\n";
        }
    }
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}