生成树相关问题

发表于 | 分类于 | 阅读次数:

##最大最小生成树
###模板
思路：将边排序，依次向并查集里加边，并且保证此边连接的两个结点不在一个并查集里，加到N-1（N为图中结点数）条边时，就生成了最小生成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int ecnt;
struct node{int from,to,value;} edge[100001];
void add(int from,int to,int value)
{
	ecnt++;
	edge[ecnt].from=from;
	edge[ecnt].to=to;
	edge[ecnt].value=value;
}
int fath[100001];
int getfath(int x)
{
	if(fath[x]==x) return x;
	return fath[x]=getfath(fath[x]);
}
void unionset(int x,int y){fath[getfath(x)]=getfath(y);}
int cmp(const node &a,const node &b)
{
	if(a.value<b.value) return true;
	else return false;
}
long long mstv=0,biancnt=0;
int main()
{
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	int from,to,value;int x;
	for(int i=1;i<=m;i++)
	{
		cin>>from>>to>>value;
		add(from,to,value);
	}
	for(int i=1;i<=n;i++) fath[i]=i;
	sort(edge+1,edge+ecnt+1,cmp);
	for(int i=1;i<=m;i++)
	{
		if(getfath(edge[i].from)!=getfath(edge[i].to))
		{
			unionset(edge[i].from,edge[i].to);
			mstv+=edge[i].value;
			biancnt++;
		}
		if(biancnt==n-1) break;
	}
	cout<<mstv;
    return 0;
}

###UVa1395 Slim_Span

所谓的Slim Span即为最大边与最小边差值最小的生成树，与最小生成树问题的思路相似

先对边升序排序，对于一个连续的边区间$[L,R]$，从小到大枚举L，对于每个L，从小到大枚举R，依次向并查集里加边，加个判断：如果目前的这些边已经使得图连通，就停止枚举，并更新最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAXN=100,MAXM=50*99,INF=1<<30;

struct node2{int u,v,w;} a[MAXM+1];int acnt;
void add2(int u,int v,int w){++acnt,a[acnt].u=u,a[acnt].v=v,a[acnt].w=w;}

int fa[MAXN+1];
int getfa(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=getfa(fa[x]);
}

void join(int x,int y)
{
	fa[getfa(x)]=getfa(y);
}

bool cmp(const node2 & a,const node2 & b){return a.w<b.w;}

int N,M;

int main()
{
	int i;
	while(cin>>N>>M&&N)
	{
		acnt=0;
		for(i=1;i<=N;i++) fa[i]=i;
		for(i=1;i<=M;i++)
		{
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			add2(u,v,w);
		}sort(a+1,a+M+1,cmp);
		int L,R;
		int minv=INF;
		for(L=1;L<=M-(N-1)+1;L++)
		{
			for(i=1;i<=N;i++) fa[i]=i;
			int times=0;
			for(R=L;R<=M;R++)
				if(getfa(a[R].u)!=getfa(a[R].v))
				{
					join(a[R].u,a[R].v);
					++times;
					if(times==N-1)
					{
						minv=min(minv,a[R].w-a[L].w);
						break;
					}
				}
		}
		if(minv==INF) cout<<-1<<endl;
		else cout<<minv<<endl;
	}
	return 0;
}

##最短路生成树
由于建树之前需要求最短路，而多数情况下还需要对生成树进行操作，所以需要建两个图。
###模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int N,M,S;
struct E{int next,from,to,value;};
struct CFS
{
	E e[MAXM];
	int ecnt,G[MAXN];
	void addEdge(int u,int v,int w)
	{e[++ecnt]=(E){G[u],u,v,w};G[u]=ecnt;}
} G,T;

struct HN
{
	int id,v,eid;
	bool operator <(const HN & ot)const
	{return v>ot.v;}
};

priority_queue<HN> heap;

int outdgr[MAXN];

int dis[MAXN];bool vis[MAXN];
void dijkstra()
{
	int i;
	for(i=1;i<=N;i++) dis[i]=INF;
	dis[1]=0;
	heap.push((HN){1,0,0});
	while(!heap.empty())
	{
		HN rn=heap.top();heap.pop();
		int u=rn.id;
		if(vis[u]) continue;
		vis[u]=true;
		if(rn.eid)
		{
			E te=G.e[rn.eid];
			T.addEdge(te.from,te.to,te.value);
			outdgr[te.from]++;
		}
		for(i=G.G[u];i;i=G.e[i].next)
		{
			int v=G.e[i].to;
			if(vis[v]) continue;
			if(dis[v]>dis[u]+G.e[i].value)
			{
				dis[v]=dis[u]+G.e[i].value;
				heap.push((HN){v,dis[v],i});
			}
		}
	}
}

方差（复数）生成树

这种问题就拓展的比较远了，不过还是基于 Kruskal 算法的，只不过数学上计算比较复杂。

小P的生成树

题目描述

小 P 是个勤于思考的好孩子，自从学习了最大生成树后，他就一直在想：能否江边全范围从实数推广到复数呢？可是马上小 P 就发现了问题，复数之间的大小关系并没有定义。于是对于任意两个复数 $z_1,z_2$ ，小 P 定义 $z_1<z_2$ 当且仅当 $|z_1|<|z_2|$ 。

现在，给出一张 n 个点 m 条边的简单无向带权图，小 P 想问你，如果按照他对复数大小关系的定义，这个图的最大生成树是什么？

输入格式

输入的第一行为两个正整数 n 和 m ，分别表示这个无向图的点数和边数。

接下来 m 行，每行四个整数 $u,v,a,b \ (1\leq u,v\leq n,\ -1000\leq a,b\leq1000)$ ，表示点 u 与 点 v 之间有一条无向边，其边权为 $a+b_i$ 。

输出格式

输出仅有一个实数，所求的最大生成树中所有边权之和的模长。

实数四舍五入，保留六位小数。

样例

样例输入

3 3
1 2 1 3
2 3 2 2
3 1 3 1

样例输出

5.830952

样例解释

显然，从该图三边中任取两条便可以构成一棵生成树，这三棵生成树的边权之和分别为 $z_1=3+5i,\ z_2=4+4i,\ z_3=5+3i$ ，其中 $|z_2|=\sqrt{32}<|z_1|=|z_3|=\sqrt{34}$ 。

数据范围

对于 $10%$ 的数据： $n\leq6$ ；
对于 $30%$ 的数据： $n\leq12$ ；
对于另外 $20%$ 的数据：每条边的边权均为实数；
对于 $100%$ 的数据： $n\leq50,\ m\leq200$ ，给定的无向图至少存在一个生成树。

提示

简单无向图的定义为：没有任何重边和自环的无向图。
若复数 $z_1=a_1+b_1i,\ z_2=a_2+b_2i$ ，则 $z_1+z_2=(a_1+a_2)+(b_1+b_2)i$ 。

这道题将最大生成树的定义由实数推广到了复数，我们注意到其实本质上就是由一维推广到二维，所以我们可以把复数视为向量。如果结果向量的方向确定，那么就可以将问题转化为正常的 Kruskal 求解了。但是我们要想直接算出最后的答案向量的方向是不现实的，所以我们考虑枚举答案向量的方向的方向，然后求最值。

这里我们发现：对于任意两条边 $e_i,e_j$ ，总有两种情况，两向量在最终向量方向上的投影（即对答案的贡献）相等。记此时向量与 x轴 夹角为 $\theta$ ， $e_i,e_j$ 的值的 $a,b$ 分别为 $a_i,b_i,a_j,b_j$，则有 $a_i\cos\theta+b_i\sin\theta=a_j\cos\theta+b_j\cos\theta$ 。而这两个角度正好为这两条边对答案贡献大小关系的分界线。当我们对任意一对边都进行过上述计算后可以将一个周角分为若干个部分，在每个部分内，每条边对于答案贡献的大小关系是一定的，我们可以对于每个部分跑一次 Kruskal 取最大值即可的出最终答案。

我们的思路现在已经成型，但是在编写时会出现一个问题：我们在求 $\theta$ 角时用到了 stl 中的 artan() ，然而此函数是以 $-\frac{\pi}{2}$ 和 $\frac{3\pi}{2}$ 为周角的，也就是说在 y轴负半轴的两侧性质是不同的，所以我们需要在 $-\frac{\pi}{2}$ 和 $\frac{3\pi}{2}$ 这两个角度处加两条分界线。至此，算法结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int MAXN=55,MAXM=205;
const double PI=acos(-1);

int n,m;

struct E{int u,v,a,b;double mod;} e[MAXM];
bool cmp(const E & x,const E & y)
{return x.mod>y.mod;}

int fa[MAXN];
void init(){for(int i=1;i<=n;i++) fa[i]=i;}
int calAnc(int x)
{return fa[x]==x?x:fa[x]=calAnc(fa[x]);}
void join(int x,int y)
{fa[calAnc(x)]=calAnc(y);}

double theta[MAXM*MAXM<<1];int pcnt;//part num
inline void calTheta()
{
	int i,j;
	double tmp;
	for(i=1;i<m;i++)
		for(j=i+1;j<=m;j++)
		{
			if(e[i].b==e[j].b)
				tmp=PI/2.0;
			else tmp=double(e[i].a-e[j].a)/(e[j].b-e[i].b),
				tmp=atan(tmp);
			theta[++pcnt]=tmp;
			theta[++pcnt]=tmp+PI;
		}
	theta[++pcnt]=-PI/2.0;
	theta[++pcnt]=3*PI/2.0;
	sort(theta+1,theta+pcnt+1);
	pcnt=unique(theta+1,theta+pcnt+1)-(theta+1);
}

inline double kruskal()
{
	int i,j,k,suma,sumb;
	double ans=0;
	for(i=1;i<pcnt;i++)
	{
		double ang=(theta[i]+theta[i+1])/2,
			   x=cos(ang),y=sin(ang);
		init();
		for(j=1;j<=m;j++) e[j].mod=e[j].a*x+e[j].b*y;
		sort(e+1,e+m+1,cmp);
		suma=sumb=0;
		for(j=1,k=0;j<=m;j++)
		{
			int u=e[j].u,v=e[j].v;
			if(calAnc(u)!=calAnc(v))
			{
				join(u,v);
				suma+=e[j].a,sumb+=e[j].b;
				if(++k==n-1) break;
			}
		}
		double sum=suma*suma+sumb*sumb;
		ans=max(ans,sum);
	}
	return sqrt(ans);
}

int main()
{
	freopen("mst.in","r",stdin);
	freopen("mst.out","w",stdout);
	int i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		int u,v,a,b;scanf("%d%d%d%d",&u,&v,&a,&b);
		e[i]=(E){u,v,a,b};
	}
	calTheta();
	printf("%.6lf\n",kruskal());
	return 0;
}

##生成树与分治

现在貌似很流行用线段树维护生成树的题目，这几天都见了两道了。

有一道 Dash Speed 思路很好，不过由于它主要是考察 CDQ分治 ，所以就不贴了，可以戳这个 Dash Speed 。

###公路建设 Highway
Time limit: 2 seconds
Memory limit: 512 megabytes

在Byteland 一共有n 个城市，编号依次为 1 到 n，它们之间计划修建 m 条双向道路，其中修建第 i 条道路的费用为 $c_i$ 。Byteasar 作为 Byteland 公路建设项目的总工程师，他决定选定一个区间 $[l,r]$，仅使用编号在该区间内的道路。他希望选择一些道路去修建，使得连通块的个数尽量少，同时，他不喜欢修建多余的道路，因此每个连通块都可以看成一棵树的结构。

为了选出最佳的区间，Byteasar 会不断选择 q 个区间，请写一个程序，帮助 Byteasar 计算每个区间内修建公路的最小总费用。

输入格式

第一行包含三个正整数 n,m,q，表示城市数、道路数和询问数。
接下来 m 行，每行三个正整数 $u_i,v_i,c_i$，表示一条连接城市 $u_i$ 和 $v_i$ 的双向道路，费用为 $c_i$ 。
接下来 q 行，每行两个正整数 $l_i,r_i$，表示一个询问。

输出格式

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

样例
highway.in

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

highway.out

7
13

数据范围

对于 $100%$ 的数据，$1 \leq ui; vi \leq n; ui \neq vi; 1 \leq li \leq ri \leq m; 1 \leq ci \leq 106$。

测试点编号 n m q 约定
$1,2,3$ $\leq1000$ $\leq1000$ $\leq1000$ 无
$4,5,6$ $\leq100$ $\leq100000$ $\leq15000$ $c_i=i$
$7,8,9,10$ $\leq100$ $\leq100000$ $\leq15000$ 无 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN=105,MAXM=1e5+5;

int n,m,q;

struct E{int u,v,w;} e[MAXM];

int fa[MAXN];
void initFa(){for(int i=1;i<=n;i++) fa[i]=i;}
int calAnc(int x)
{return fa[x]==x?x:fa[x]=calAnc(fa[x]);}

struct K{int eid[MAXN],sum;K(){sum=0;memset(eid,0,sizeof(eid));}};

struct TN
{
	int lc,rc,l,r;K k;
	TN(){lc=rc=l=r;k=K();}
} t[MAXM<<1];int tcnt,root=1;

K merge(K x,K y)
{
	int tmp[MAXN<<1],tmpcnt=0;
	memset(tmp,0,sizeof(tmp));
	int i=1,j=1,k=0;
	while(e[x.eid[i]].w&&e[y.eid[j]].w)
		if(e[x.eid[i]].w<e[y.eid[j]].w)
			tmp[++k]=x.eid[i++];
		else tmp[++k]=y.eid[j++];
	while(e[x.eid[i]].w) tmp[++k]=x.eid[i++];
	while(e[y.eid[j]].w) tmp[++k]=y.eid[j++];
	initFa();
	K res;
	int * eid=res.eid;
	int ecnt=0;
	for(i=1;i<=k;i++)
	{
		int uAnc=calAnc(e[tmp[i]].u),vAnc=calAnc(e[tmp[i]].v);
		if(uAnc!=vAnc)
		{
			fa[uAnc]=vAnc;
			eid[++ecnt]=tmp[i];
			res.sum+=e[tmp[i]].w;
		}
	}
	return res;
}

void build(int o,int l,int r)
{
	t[o].l=l,t[o].r=r;
	if(l==r) {t[o].k.sum=e[l].w,t[o].k.eid[1]=l;return;}
	int mid=(l+r)>>1;
	t[o].lc=++tcnt;build(t[o].lc,l,mid);
	t[o].rc=++tcnt;build(t[o].rc,mid+1,r);
	t[o].k=merge(t[t[o].lc].k,t[t[o].rc].k);
}

K query(int o,int l,int r)
{
	if(l==t[o].l&&r==t[o].r) return t[o].k;
	int mid=(t[o].l+t[o].r)>>1;
	if(r<=mid) return query(t[o].lc,l,r);
	else if(l>mid) return query(t[o].rc,l,r);
	else return merge(query(t[o].lc,l,mid),query(t[o].rc,mid+1,r));
}

int main()
{
	freopen("highway.in","r",stdin);
	freopen("highway.out","w",stdout);
	int i;
	scanf("%d%d%d",&n,&m,&q);
	for(i=1;i<=m;i++)
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	tcnt=1;build(root,1,m);
	for(i=1;i<=q;i++)
	{
		int l,r;scanf("%d%d",&l,&r);
		printf("%d\n",query(root,l,r).sum);
	}
	return 0;
}