BZOJ5216: [Lydsy2017省队十连测]公路建设
? 解题记录 ? ? BZOJ ? ? 并查集 ? ? 线段树 ? ? Kruscal ?    2018-09-25 08:06:17    343    0    0

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

Claris原创,本站版权所有

注意到点只有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;
}


上一篇: BZOJ5218: [Lydsy2017省队十连测]友好城市

下一篇: BZOJ5215: [Lydsy2017省队十连测]商店购物

343 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航