题解：AT_icpc2013spring_e 最小生成树

coding_goat · 2025-09-28 19:19:46 · 题解

这不是我们【数据删除】原题吗，下次使用请表明出处。

首先我们感受到跑出来一颗最小生成树之后，断树边之后再在外面找一条最小的能连接两棵树的边是最优的。

证明：假设有一条不连接两个不连通的边会被加入最终答案里面，那么就会在跑 MST 的时候被加入进去，不会出现在这里。

其次我们对于每条树外的边考虑它能对哪些东西造成贡献。一条连接 u,v 的边能被选中，当且仅当断掉的边为 u 在树上到 v 的路径。所以就变成了一个给一条路径对边权取 \min 的一个过程了。

前面跑 MST 可以用 Kruskal，这部分时间复杂度 O(m\log m)；后面可以用树剖实现，这部分时间复杂度 O(n \log^2 n)。

#include<bits/stdc++.h>

#define pii pair<int,int> 
#define pll pair<long long,long long> 
#define ll long long
#define i128 __int128

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define in4(a,b,c,d) a=read(), b=read(), c=read(), d=read()
#define fst first 
#define scd second 
#define dbg puts("IAKIOI")

using namespace std;

int read() {
    int x=0,f=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); 
    for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }

const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }

#define maxn 200050

int n,m;
struct edge{
    int u,v,d,idx;
    bool operator<(const edge &x) const {
        return d<x.d;
    }
}ed[maxn];
bool vis[maxn];
vector<int> G[maxn];
struct Dsu {
    int fa[maxn];
    void pre(int n) {
        For(i,1,n) fa[i]=i;
    }
    int fnd(int x) {return fa[x]==x?fa[x]:fa[x]=fnd(fa[x]); }
    void uni(int x,int y) {
        fa[fnd(x)]=fnd(y);
    }
}dsu;

struct node {
    int dep,fa,siz,mxs;
    int dfn,top;
}tr[maxn]; int dfntop;

void dfs1(int u,int fa) {
    tr[u].fa=fa,tr[u].dep=tr[fa].dep+1;
    tr[u].siz=1;
    for(auto v:G[u]) if(v!=fa) {
        dfs1(v,u);
        tr[u].siz+=tr[v].siz;
        if(tr[v].siz>tr[tr[u].mxs].siz) tr[u].mxs=v;
    }
}
void dfs2(int u,int Ltop) {
    tr[u].dfn=++dfntop; tr[u].top=Ltop;
    if(tr[u].mxs) dfs2(tr[u].mxs,Ltop);
    for(auto v:G[u]) if(v!=tr[u].fa&&v!=tr[u].mxs) dfs2(v,v);
}

struct SegT {
    struct Tnode {
        int mn,tag;
    }tr[maxn<<2];
    void psu(int idx) {
        tr[idx].mn=min(tr[lc(idx)].mn,tr[rc(idx)].mn);
    }
    void psd(int idx,int l,int r) {
        if(tr[idx].tag==1e9) return ;
        tr[lc(idx)].mn=min(tr[lc(idx)].mn,tr[idx].tag);
        tr[rc(idx)].mn=min(tr[rc(idx)].mn,tr[idx].tag);
        tr[lc(idx)].tag=min(tr[lc(idx)].tag,tr[idx].tag);
        tr[rc(idx)].tag=min(tr[rc(idx)].tag,tr[idx].tag);
        tr[idx].tag=1e9;
    }
    void build(int idx,int l,int r) {
        tr[idx].mn=tr[idx].tag=1e9;
        if(l==r) return ;
        int mid=l+r>>1;
        build(lc(idx),l,mid);
        build(rc(idx),mid+1,r);
        psu(idx);
    }
    void modi(int idx,int l,int r,int L,int R,int val) {
        if(L<=l&&r<=R) {
            tr[idx].mn=min(tr[idx].mn,val);
            tr[idx].tag=min(tr[idx].tag,val);
            return;
        }
        psd(idx,l,r);
        int mid=l+r>>1;
        if(L<=mid) modi(lc(idx),l,mid,L,R,val);
        if(R>mid) modi(rc(idx),mid+1,r,L,R,val);
        psu(idx);
    }
    int query(int idx,int l,int r,int L,int R) {
        if(L<=l&&r<=R) return tr[idx].mn;
        int mid=l+r>>1,res=1e9; psd(idx,l,r);
        if(L<=mid) res=query(lc(idx),l,mid,L,R);
        if(R>mid) res=min(res,query(rc(idx),mid+1,r,L,R));
        return res;
    }
}Tr;

void add(int u,int v,int c) {
    while(tr[u].top!=tr[v].top) {
        if(tr[tr[u].top].dep<tr[tr[v].top].dep) swap(u,v);
        Tr.modi(1,1,n,tr[tr[u].top].dfn,tr[u].dfn,c);
        u=tr[tr[u].top].fa;
    }
    if(tr[u].dep>tr[v].dep) swap(u,v);
    if(tr[u].dep<tr[v].dep) Tr.modi(1,1,n,tr[u].dfn+1,tr[v].dfn,c);
}

int query(int u,int v) {
    int res=1e9;
    while(tr[u].top!=tr[v].top) {
        if(tr[tr[u].top].dep<tr[tr[v].top].dep) swap(u,v);
        res=min(res,Tr.query(1,1,n,tr[tr[u].top].dfn,tr[u].dfn));
        u=tr[tr[u].top].fa;
    }
    if(tr[u].dep>tr[v].dep) swap(u,v);
    if(tr[u].dep<tr[v].dep) res=min(res,Tr.query(1,1,n,tr[u].dfn+1,tr[v].dfn));
    return res;
}

ll totans[maxn];

void work() {
    in2(n,m);
    For(i,1,m) {
        in3(ed[i].u,ed[i].v,ed[i].d);
        ed[i].idx=i;
    }
    sort(ed+1,ed+m+1);
    dsu.pre(n);
    ll ans=0;
    For(i,1,m) {
        auto [u,v,d,idx]=ed[i];
        if(dsu.fnd(u)!=dsu.fnd(v)) {
            G[u].push_back(v);
            G[v].push_back(u);
            dsu.uni(u,v); ans+=d; vis[i]=1;
        }
    }
    dfs1(1,0);dfs2(1,1);
    Tr.build(1,1,n);
    For(i,1,m) if(!vis[i]){
        add(ed[i].u,ed[i].v,ed[i].d);
    }
    For(i,1,m) {
        if(!vis[i]) {
            totans[ed[i].idx]=ans;
        } else {
            int res=query(ed[i].u,ed[i].v);
            totans[ed[i].idx]=ans-ed[i].d+res;
            if(res==1e9) totans[ed[i].idx]=-1;
        }
    }
    For(i,1,m) cout<<totans[i]<<'\n';
}

signed main() {
//  freopen("data.in","r",stdin);
//  freopen("myans.out","w",stdout);
//  ios::sync_with_stdio(false); 
//  cin.tie(0); cout.tie(0);
    double stt=clock();
    int _=1;
//  _=read();
//  cin>>_;
    For(i,1,_) {
        work();
    }
    cerr<<"\nTotal Time is:"<<(clock()-stt)*1.0/1000<<" second(s)."<<'\n';
    return 0;
}