NKOJ 2991 （NOI 2014） 魔法森林 （动态树+最小生成树）

发表于 |
字数统计: 1,021字 | 阅读时长 ≈ 6min

P2991【NOI2014 Day1】魔法森林

问题描述
这里写图片描述

输入格式

这里写图片描述
输出格式
这里写图片描述

样例输入1

4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17

样例输入2

3 1
1 2 1 1

样例输出1

32

样例输出2

-1

数据范围
这里写图片描述

注意到这道题每条边有两个权值，所求为经过路径上每种权值的最大值之和的最小值。

考虑只有一种权值，那么显然最小生成树。
考虑有两种权值，那么将边按一种权值排序，从小到大讨论，维护另一种权值的最小生成树，而当前的答案 就是当前边的第一种权值，加上另一种权值的最小生成树上从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
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 500005
using namespace std;
struct node{int x,y,a,b,id;}edge[N];
int n,m,S[N],top,Hash[N],F[N],ans;
int ls[N],rs[N],fa[N],v[N],Max[N],id[N],rev[N];
int GF(int x)
{
	if(F[x]!=x)F[x]=GF(F[x]);
	return F[x];
}
bool cmp(node aa,node bb)
{return aa.a<bb.a;}
int GM(int x,int y,int z)
{
	if(x>=y&&x>=z)return x;
	if(y>=z)return y;
	return z;
}
bool Isroot(int x)
{return ls[fa[x]]!=x&&rs[fa[x]]!=x;}
void MT(int x)
{
	Max[x]=GM(v[x],Max[ls[x]],Max[rs[x]]);
	if(Max[x]==v[x])id[x]=x;
	else if(Max[x]==Max[ls[x]])id[x]=id[ls[x]];
	else id[x]=id[rs[x]];
}
void PD(int x)
{
	if(rev[x])
	{
		swap(ls[x],rs[x]);
		rev[ls[x]]^=1;
		rev[rs[x]]^=1;
		rev[x]^=1;
	}
}
void Zig(int x)
{
	int y=fa[x],z=fa[y];
	if(!Isroot(y))y==ls[z]?ls[z]=x:rs[z]=x;fa[x]=z;
	ls[y]=rs[x];fa[rs[x]]=y;
	rs[x]=y;fa[y]=x;
	MT(y);MT(x);
}
void Zag(int x)
{
	int y=fa[x],z=fa[y];
	if(!Isroot(y))y==ls[z]?ls[z]=x:rs[z]=x;fa[x]=z;
	rs[y]=ls[x];fa[ls[x]]=y;
	ls[x]=y;fa[y]=x;
	MT(y);MT(x);
}
void Splay(int x)
{
	int i,y,z;
	S[++top]=x;
	for(i=x;!Isroot(i);i=fa[i])S[++top]=fa[i];
	while(top)PD(S[top--]);
	while(!Isroot(x))
	{
		y=fa[x];z=fa[y];
		if(!Isroot(y))
		{
			if(y==ls[z])x==ls[y]?(Zig(y),Zig(x)):(Zag(x),Zig(x));
			else x==rs[y]?(Zag(y),Zag(x)):(Zig(x),Zag(x));
		}
		else x==ls[y]?Zig(x):Zag(x);
	}
}
void Access(int x)
{
	for(int t=0;x;x=fa[x])
	{
		Splay(x);
		rs[x]=t;
		MT(x);t=x;
	}
}
void Makeroot(int x)
{
	Access(x);
	Splay(x);
	rev[x]^=1;
}
int Findroot(int x)
{
	Access(x);
	Splay(x);
	while(ls[x])x=ls[x];
	return x;
}
void Link(int x,int y)
{
	Makeroot(x);
	fa[x]=y;
}
void Cut(int x,int y)
{
	Makeroot(x);
	Access(y);
	Splay(y);
	ls[y]=fa[x]=0;
}
bool Kruscal()
{
	int i,j,k,x,y,cnt;bool f=0;
	for(i=1;i<=n;i++)F[i]=i;
	i=1;cnt=0;ans=1e9;
	while(i<=m)
	{
		x=GF(edge[i].x);
		y=GF(edge[i].y);
		if(x!=y)
		{
			F[x]=y;cnt++;
			Link(edge[i].x,edge[i].id);
			Link(edge[i].y,edge[i].id);
		}
		else
		{
			Makeroot(edge[i].x);
			Access(edge[i].y);
			Splay(edge[i].y);
			if(Max[edge[i].y]>edge[i].b)
			{
				k=Hash[id[edge[i].y]];
				Cut(edge[k].x,edge[k].id);
				Cut(edge[k].y,edge[k].id);
				Link(edge[i].x,edge[i].id);
				Link(edge[i].y,edge[i].id);
			}
		}
		if(f||Findroot(1)==Findroot(n))
		{
			Makeroot(1);
			Access(n);
			Splay(n);
			ans=min(ans,edge[i].a+Max[n]);
			f=1;
		}
		i++;
	}
	if(f)return 1;
	return 0;
}
int main()
{
	int i,x,y;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)scanf("%d%d%d%d",&edge[i].x,&edge[i].y,&edge[i].a,&edge[i].b),edge[i].id=n+i;
	sort(edge+1,edge+m+1,cmp);
	for(i=1;i<=m;i++)Hash[edge[i].id]=i,v[edge[i].id]=edge[i].b;
	if(Kruscal())printf("%d",ans);
	else printf("-1");
}