题解：P14415 [JOISC 2015] 遗产继承 / Inheritance

· · 题解

闲话

什么日本神题

被大手子拉过来刷题了。

正文

看了一眼，简化一下题意。

形式化题面

给定 n 个点，m 条带权无向边，要求删去 k 轮边，满足删去的边不成环且边权最大，无满足则不删。最后输出每条边在第几轮删去，若未删去则输出 0。

暴力

直接跑 k 遍最大生成树，时间复杂度为 \Theta(k\times m\times \log _2m\times \alpha(n))，直接炸缸。

正解

根据大手子の情报根据直觉，删边的顺序存在单调性。

具体而言，假如一条边在第 i 轮被删去，则它不可能会在之后被删，因为这对于第 i 轮不优；它同样不会在之前被删，因为这对于之前的轮数不优。

由此我们考虑维护 k 个并查集，其中第 i 个维护第 i 轮所选的边。对于第 i 条边，我们依据单调性进行二分，求出该边最早在哪个并查集里满足不会构成环，二分结束后将第 i 条边加入所属的并查集。

单次二分时间复杂度为 \Theta( \log _2k \times \alpha(n))，总共进行 m 轮，再加上原先的排序，总复杂度为 \Theta(m\times \log _2k \times \alpha(n)+m \log _2m)，稳稳通过。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector
#define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define pb push_back
const int INF=1e9+10;
struct node{
    int chos,u,v,w,id;
    friend bool operator <(const node &a,const node &b){
        if(a.chos^b.chos) return a.chos<b.chos;
        if(a.w^b.w) return a.w>b.w;
        if(a.id^b.id) return a.id<b.id;
        if(a.u^b.u) return a.u<b.u;
        return a.v<b.v;
    }
};
struct DSU{
    V<int>fa;
    DSU(int _n):fa(_n+1){iota(fa.begin(),fa.end(),0);}
    int fin(int x){
        while(x^fa[x])x=fa[x]=fa[fa[x]];
        return x;
    }
    bool is_(int u,int v){
        return fin(u)==fin(v);
    }
    void merge(int u,int v){
        if(is_(u,v)) return;
        u=fin(u),v=fin(v);
        fa[u]=v;
    }
};
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m,k;cin>>n>>m>>k;
    V<DSU> dsu(k+1,DSU(n));
    V<node>e(m+1);
    FOR(i,1,m){
        cin>>e[i].u>>e[i].v>>e[i].w;e[i].chos=0;e[i].id=i;
    }
    V<int>ans(m+1,0);
    sort(e.begin()+1,e.end());
    auto check=[&](int edge,int x){
        return dsu[x].is_(e[edge].u,e[edge].v);
    };
    FOR(i,1,m){
        int l=1,r=k,res=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(i,mid)){
                l=mid+1;
            }else{
                res=mid;
                r=mid-1;
            }
        }
        if(res){
            ans[e[i].id]=res;
            dsu[res].merge(e[i].u,e[i].v);
        }
    }
    FOR(i,1,m) cout<<ans[i]<<"\n";
    return 0;
}