【XSY3810】公路建设（线段树，kruskal）

题面

题解

一开始竟然没反应过来是最小生成树。

考虑用线段树直接维护每个区间的答案。

注意到一个区间最多只有 $n-1$ 条树边有用，所以线段树每个节点用一个 vector按权值从小到大保存区间内用到的树边即可。

合并两个区间的信息时，只需要将两棵子树存的树边归并排序，然后做 Kruskal 算法。

时间复杂度 $O((m+q\log m)n\alpha (n))$。

#include<bits/stdc++.h>

#define N 110
#define M 100010

using namespace std;

struct edge
{
	int u,v,w;
}e[M];

struct data
{
	int sum;
	vector<edge>v;
	data()
	{
		sum=0;
		v.clear();
	}
}t[M<<2];

int n,m,q,fa[N];

vector<edge>tmp;

void Sort(vector<edge>a,vector<edge>b)
{
	tmp.clear();
	int cnta=0,cntb=0,size1=a.size(),size2=b.size();
	while(cnta<size1&&cntb<size2)
	{
		if(a[cnta].w<b[cntb].w)
		{
			tmp.push_back(a[cnta]);
			cnta++;
		}
		else
		{
			tmp.push_back(b[cntb]);
			cntb++;
		}
	}
	while(cnta<size1)
	{
		tmp.push_back(a[cnta]);
		cnta++;
	}
	while(cntb<size2)
	{
		tmp.push_back(b[cntb]);
		cntb++;
	}
}

int find(int x)
{
	return x==fa[x]?x:(fa[x]=find(fa[x]));
}

data Kruskal()
{
	data ans;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=0,size=tmp.size(),tot=0;i<size&&tot<n-1;i++)
	{
		int a=find(tmp[i].u),b=find(tmp[i].v);
		if(a!=b)
		{
			fa[a]=b;
			tot++;
			ans.v.push_back(tmp[i]);
			ans.sum+=tmp[i].w;
		}
	}
	return ans;
}

void build(int k,int l,int r)
{
	if(l==r)
	{
		if(n>1)
		{
			t[k].v.push_back(e[l]);
			t[k].sum=e[l].w;
		}
		return;
	}
	int mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	Sort(t[k<<1].v,t[k<<1|1].v);
	t[k]=Kruskal();
//	printf("l=%d r=%d edge=",l,r);
//	for(int i=0,size=t[k].v.size();i<size;i++)
//		printf("(%d,%d,%d) ",t[k].v[i].u,t[k].v[i].v,t[k].v[i].w);
//	printf("sum=%d
",t[k].sum);
}

data query(int k,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr) return t[k];
	int mid=(l+r)>>1;
	if(qr<=mid) return query(k<<1,l,mid,ql,qr);
	if(ql>mid) return query(k<<1|1,mid+1,r,ql,qr);
	Sort(query(k<<1,l,mid,ql,qr).v,query(k<<1|1,mid+1,r,ql,qr).v);
	return Kruskal();
}

int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	build(1,1,m);
	while(q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d
",query(1,1,m,l,r).sum);
	}
	return 0;
}
/*
3 5 2
1 3 2
2 3 1
2 1 6
3 1 7
2 3 7
2 5
3 4
*/