BZOJ

分析

考虑一个很暴力的思路。

以边的编号为下标建一棵线段树,每个节点开一个 vector 存一下对应区间内哪些边在最小生成森林内。

这样子合并两个节点就是先 std::merge 得到排好序的边集,然后 Kruskal 求最小生成森林。

查询就把每个区间合并起来就好了。

然后它压着时限过了...

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10,M=100000+10;

int n,m,q;

struct edge { int u,v,w; } e[M];
bool operator <(edge a,edge b) { return a.w<b.w; }

int f[N];
inline int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

struct node {
    int ans; vector<edge> e;
    node() { ans=0,e.clear(); }
};
node operator +(node x,node y) {
    node res; vector<edge> tmp; tmp.clear();
    merge(x.e.begin(),x.e.end(),y.e.begin(),y.e.end(),back_inserter(tmp));
    for (re int i=1;i<=n;++i) f[i]=i;
    for (re int i=0;i<tmp.size();++i) {
        int p=find(tmp[i].u),q=find(tmp[i].v);
        if (p!=q) {
            res.ans+=tmp[i].w;
            res.e.push_back(tmp[i]);
            f[p]=q;
        }
    }
    return res;
}

#define ls (o<<1)
#define rs (o<<1|1)
node t[M<<2];
inline void build(int o,int l,int r) {
    if (l==r) {
        t[o].ans=e[l].w;
        t[o].e.push_back(e[l]);
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    t[o]=t[ls]+t[rs];
}
inline node query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return t[o];
    int mid=(l+r)>>1;
    if (qr<=mid) return query(ls,l,mid,ql,qr);
    else if (ql>mid) return query(rs,mid+1,r,ql,qr);
    else return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr);
}
#undef ls
#undef rs

int main() {
    n=read(),m=read(),q=read();
    for (re int i=1;i<=m;++i) e[i]=(edge){read(),read(),read()};
    build(1,1,m);
    while (q--) {
        int l=read(),r=read();
        printf("%d\n",query(1,1,m,l,r).ans);
    }
    return 0;
}
最后修改:2019 年 10 月 30 日 08 : 47 AM