BZOJ5216: [Lydsy2017省队十连测]公路建设

Description

在Byteland一共有n个城市，编号依次为1到n，它们之间计划修建m条双向道路，其中修建第i条道路的费用为ci。B

yteasar作为Byteland公路建设项目的总工程师，他决定选定一个区间[l,r]，仅使用编号在该区间内的道路。他希

望选择一些道路去修建，使得连通块的个数尽量少，同时，他不喜欢修建多余的道路，因此每个连通块都可以看成

一棵树的结构。为了选出最佳的区间， Byteasar会不断选择 q个区间，请写一个程序，帮助 Byteasar计算每个区

间内修建公路的最小总费用。

Input

第一行包含三个正整数n; m; q，表示城市数、道路数和询问数。

接下来m 行，每行三个正整数ui; vi; ci，表示一条连接城市ui 和vi 的双向道路，费用为ci。

接下来q 行，每行两个正整数li; ri，表示一个询问。

1 ≤ ui, vi ≤ n, ui ̸= vi, 1 ≤ li ≤ ri ≤ m, 1 ≤ ci ≤ 10^6

N<=100,M<=100000,Q<=15000

Output

输出q 行，每行一个整数，即最小总费用。

Sample Input

3 5 2
1 3 2
2 3 1
2 1 6
3 1 7
2 3 7
2 5
3 4

Sample Output

7
13

HINT

Source

注意到点只有100个，那么作为答案的边最多只有99条。线段树一个节点强行暴力记录当前区间的答案边。然后我们考虑合并，发现合并两个区间做一次Kruscal就行了，复杂度O(100)。那么外层一个线段树，更新操作Kruscal，查询操作log次Kruscal。就可以了。

#include<cstdio>
#include<vector>
using namespace std;
const int maxn = 1e5 + 5;
struct edge {
	int u, v, w;
}e[maxn << 1];
int n, m, q, L, R;

namespace DSU {
	int fa[105];
	void init(int n) {
		for(register int i = 1; i <= n; ++i)
			fa[i] = i;
	}
	int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void combine(int y, int x) {
		fa[find(y)] = find(x);
	}
}

namespace SGT {
	struct node {
		vector<int > es;
	} t[maxn << 2];
	vector<int > rt;
	int cnt, tmp, pl, pr, Llen, Rlen;
	void gao(int x) {
		using namespace DSU;
		if(find(e[x].u) != find(e[x].v)) 
			rt.push_back(x), DSU::combine(e[x].u, e[x].v);
	}
	vector<int > merge(const vector<int > & lc, const vector<int > & rc) {
		DSU::init(n);
		rt.clear(), pl = pr = 0, Llen = lc.size(), Rlen = rc.size();
		while(pl < Llen && pr < Rlen)
			if(e[lc[pl]].w < e[rc[pr]].w) gao(lc[pl++]);
			else gao(rc[pr++]);
		while(pl < Llen) gao(lc[pl++]);
		while(pr < Rlen) gao(rc[pr++]);
		return rt;
	}
	void push_up(int rt) {
		t[rt].es = merge(t[rt << 1].es, t[rt << 1 | 1].es);
	}
	void build(int l, int r, int rt) {
		if(l == r) return t[rt].es.push_back(l), void();
		int mid = l + r >> 1;
		build(l, mid, rt << 1);
		build(mid + 1, r, rt << 1 | 1);
		push_up(rt);
	}
	vector<int > query(int l, int r, int tl, int tr, int rt) {
		if(l == tl && r == tr) return t[rt].es;
		int mid = tl + tr >> 1;
		if(r <= mid) return query(l, r, tl, mid, rt << 1);
		else if(l > mid) return query(l, r, mid + 1, tr, rt << 1 | 1);
		else return merge(query(l, mid, tl, mid, rt << 1), query(mid + 1, r, mid + 1, tr, rt << 1 | 1));
	}
	int Q(int l, int r) {
		rt = query(l, r, 1, m, 1);
		tmp = rt.size(); int ans = 0;
		for(register int i = 0; i < tmp; ++i)
			ans += e[rt[i]].w;
		return ans;
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	for(register int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
	}
	SGT::build(1, m, 1);
	for(register int i = 1; i <= q; ++i) {
		scanf("%d%d", &L, &R);
		printf("%d\n", SGT::Q(L, R));
	}
	return 0;
}

Rockdu's Blog