bzoj 5216 [Lydsy2017省队十连测]公路建设线段树维护最小生成树

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

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 93 Solved: 53
[Submit][Status][Discuss]

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

题解：因为点数极少所以有用的边只有n-1条，因为最小生成树，

　　　所以线段树每个节点维护的边只需要有用的那几条就可以了。

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<cmath>
 6 
 7 #define N 107
 8 #define M 100007
 9 #define ls p<<1
10 #define rs p<<1|1
11 using namespace std;
12 inline int read()
13 {
14     int x=0,f=1;char ch=getchar();
15     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
16     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
17     return x*f;
18 }
19 
20 int n,m,q;
21 int fz[M],fa[N];
22 struct Data
23 {
24     int x,y,z;
25 }a[M];
26 struct Node
27 {
28     int sum,a[N];
29     void init()
30     {
31         sum=0;
32         memset(a,0,sizeof(a));
33     }
34 }tr[M<<2],ans;
35 
36 int find(int x)
37 {
38     if (fa[x]!=x) fa[x]=find(fa[x]);
39     return fa[x];
40 }
41 Node merge(Node y,Node z)
42 {
43     Node x;x.init();
44     int i=1,j=1,k=0,op=0;
45     while(a[y.a[i]].z&&a[z.a[j]].z)
46         if (a[y.a[i]].z<a[z.a[j]].z) fz[++k]=y.a[i++];
47         else fz[++k]=z.a[j++];
48     while(a[y.a[i]].z) fz[++k]=y.a[i++];
49     while(a[z.a[j]].z) fz[++k]=z.a[j++];
50     for (int i=1;i<=n;i++) fa[i]=i;
51     for (int i=1;i<=k;i++)
52     {
53         int u=find(a[fz[i]].x),v=find(a[fz[i]].y);
54         if (u!=v)
55         {
56             fa[u]=v;
57             x.sum+=a[fz[i]].z,x.a[++op]=fz[i];
58         }
59     }
60     return x;
61 }
62 void build(int p,int l,int r)
63 {
64     if (l==r)
65     {
66         tr[p].sum=a[l].z;
67         tr[p].a[1]=l;
68         return;
69     }
70     int mid=(l+r)>>1;
71     build(ls,l,mid),build(rs,mid+1,r);
72     tr[p]=merge(tr[ls],tr[rs]);
73 }
74 Node tree_find(int p,int l,int r,int x,int y)
75 {
76     if (l==x&&r==y) return tr[p];
77     int mid=(l+r)>>1;
78     if (y<=mid) return tree_find(ls,l,mid,x,y);
79     else if (x>mid) return tree_find(rs,mid+1,r,x,y);
80     else return merge(tree_find(ls,l,mid,x,mid),tree_find(rs,mid+1,r,mid+1,y));
81 }
82 int main()
83 {
84     n=read(),m=read(),q=read();
85     for (int i=1;i<=m;i++)
86         a[i].x=read(),a[i].y=read(),a[i].z=read();
87     build(1,1,m);
88     while(q--)
89     {
90         int l=read(),r=read();
91         ans=tree_find(1,1,m,l,r);
92         printf("%d
",ans.sum);
93     }
94 }