【BZOJ 4883】[Lydsy2017年5月月赛] 棋盘上的守卫

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4883
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/05/ludsy_may_contest_solution.pdf

解题报告

把行和列看成点,格子看成边
那么一个$n$个点的连通块需要$n$条边
于是用$Kruskal$做一个基环树森林就可以了
时间复杂度:$O(nm \log nm)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300000;

struct Edge{
	int u, v, c;
	bool operator < (const Edge &ee) const {
		return c < ee.c;
	}
}e[N];
int n, m, tot, cir[N], fa[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

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

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	n = read(); m = read();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			e[++tot].c = read();
			e[tot].u = i;
			e[tot].v = n + j;
		}
	}
	sort(e + 1, e + 1 + tot);
	for (int i = 1; i <= n + m; i++) {
		fa[i] = i;
	}
	LL ans = 0;
	for (int i = 1; i <= tot; i++) {
		int u = e[i].u, v = e[i].v;
		int fu = find(u), fv = find(v);
		if (cir[fu] && cir[fv]) {
			continue;
		} else if (fu != fv) {
			fa[fv] = fu;
			cir[fu] |= cir[fv];
		} else if (!cir[fu]) {
			cir[fu] = 1;
		}
		ans += e[i].c;
	}
	printf("%lld\n", ans);
	return 0;
}

【BZOJ 2521】[SHOI2010] 最小生成树

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2521
神犇题解:http://krydom.com/bzoj2521/

解题报告

这题有一个非常显然的贪心:做Kruskal的时候,如果会使那条边的两个端点连在一起就暴力加权值
但这样显然也是错误的,因为我们可能是在之前的步骤就废掉一些边
于是怎么解决这个问题呢?
我们相当于不能在某两个端点之间有通路,那么这和网络流的增广路相同
于是我们把边的容量设为暴力改的时候需要的花费,然后跑一遍最小割就可以了

【BZOJ 4144】[AMPPZ2014] Petrol

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4144
神犇题解:http://www.cnblogs.com/Tunix/p/4593049.html

解题报告

随便想一想,这题似乎除了有加油站的点之外,其他点似乎完全可以不用考虑?
再仔细想一想的话,我们似乎只要求出任意两个有加油站的点的最短路,然后再做一个MST就可以了!

现在的问题就是如何求出任意两点的最短路了
我们考虑放宽一点条件,求出一些最短路径的集合 $\{ e \}$ ,使其能够凑出任意两点的最短路
现在考虑两点之间最短路的性质:

定义$blg(x)$表示离$x$最近的关键点
那么对于 $a \to b$ 最短路上,一定是前一部分$blg(x)=a$,后一部分$blg(x)=b$
于是我们就可以通过枚举原图中的一条边$(x_1,x_2)$并且判断$blg(x_1)$是否等于$blg(x_2)$来找到所有中途不经过加油站的最短路

如何证明呢?考虑反证法:如果中途有一个点$blg(y)=c$那么先从$a \to b \to c$一定不比$a \to b$劣
这是因为如果我们走到y点后绕道到c点去加油,回来的时候油量一定不少于从a点到y点的油量

这样我们就可以找到一个边集 $\{ \varepsilon \}$使得 $\{ e\} \subset \{ \varepsilon \}$
于是我们把$\{ \varepsilon \}$拿出来,做一个最小生成树,然后查询的时候,在树上倍增一下就可以啦!

【BZOJ 2001】[HNOI2010] City 城市建设

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2001
神犇题解Ⅰ:http://www.cnblogs.com/BLADEVIL/p/3512644.html
神犇题解Ⅱ:http://blog.miskcoo.com/2015/04/bzoj-2001

解题报告

如果没有边权,只需要维护连通性
那么搞一个可以撤销的并查集就可以啦!

现在考虑带边权的情况,我们仍然对时间进行分治
在每一层,我们进行两个操作:

1. Contraction 缩小点的规模

将所有当前分治区间内会被修改的边的边权置为 $-INF$
然后做一遍MST,将此时通过非 $-INF$ 连接的点用并查集缩起来
因为$-INF$边只会有区间长度个,所以每一次分治后,点的规模不会超过分治区间的长度

2. Reduction 缩小边的规模

将会被修改的边的边权置为 $INF$,然后再做一遍MST
将此时不在MST中的边删去,因为保留的边数不会超过点数,所以边的规模也不会超过分治区间的长度

所以时间复杂度写出来长这样: $T(n) = 2T(\frac{n}{2}) + n\log n$
用主定理化简之后,时间复杂度就是: $O(n{\log ^2}n)$

【AtCoder】[CODE FESTIVAL 2016 Final G] Zigzag MST

相关链接

题目传送门:http://cf16-final.contest.atcoder.jp/tasks/codefestival_2016_final_g
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/01/atcoder_codefestival_2016_final_g.pdf

解题报告

这题好神啊!现在感觉每道题都好神啊!

先来看任意一个连边操作:

考虑正常的最小生成树算法,如果用到了价值为 $ c+1$ 的边,那么价值为 $ c$ 的边一定已经考虑过了
于是我们就可以把图等价地变换为下面这个样子:

这样的话,我们可以把价值为 $ c$ 地那一类边拿出来单独考虑
余下的边搞一个堆,连一圈
这样的话,我们的图就改造成了这个样子:

此时我们的边就只剩 $ N+Q$ 条了,直接跑最小生成树算法就可以啦!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 400000+9;

struct Edge{int u,v,w;}e[N];
struct Operation{int p,c;}op[N];
priority_queue<Operation> que;
int n,m,tot,vis[N],fa[N]; LL vout;

inline bool operator < (const Edge &A, const Edge &B) {return A.w < B.w;}
inline bool operator < (const Operation &A, const Operation &B) {return A.c > B.c;}

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int find(int w) {
	int f = fa[w], tmp;
	while (f != fa[f]) f = fa[f];
	while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
	return f;
}

int main() {
	n = read(); m = read();
	for (int i=1,a,b,c;i<=m;i++) {
		a = read(); b = read(); c = read();
		e[++tot] = (Edge){a, b, c};
		que.push((Operation){a, c+1});
		que.push((Operation){b, c+2});
	}
	while (!que.empty()) {
		Operation w = que.top(); que.pop();
		if (!vis[w.p]) {
			vis[w.p] = 1;
			e[++tot] = (Edge){w.p, (w.p+1)%n, w.c};
			que.push((Operation){(w.p+1)%n, w.c+2});
		}
	}
	sort(e+1, e+1+tot);
	for (int i=0;i<=n;i++) fa[i] = i;
	for (int i=1;i<=tot;i++) {
		if (find(e[i].u) != find(e[i].v)) {
			fa[fa[e[i].u]] = fa[e[i].v];
			vout += e[i].w;
		}
	}
	printf("%lld\n",vout);
	return 0;
}

【BZOJ 1016】[JSOI2008] 最小生成树计数

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1016
优秀题解:https://blog.sengxian.com/solutions/bzoj-1016

题解

考虑最小生成树,如果使用价值相同的非树边边替换树边,得到的效果一定一样
因为不一样的话,用于替换的边就会成为最小生成树的树边
换一句话来说,权值相同的边处理完之后,图的连通性一定一样

于是暴力枚举同一权值的边的组合情况
使用并查集判断一下即可

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100+9;
const int M = 1000+9;
const int MOD = 31011;

struct Edge{int u,v,w;}e[M];
vector<Edge> que[M];
int n,m,fa[N],fa_tmp[N],_hash[M],cnt[M],tot,vout=1,vis[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int find(int w) {
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
	return f;
}

void DFS(int w, int sz, int cur, int id, int &tmp) {
	if (cur > cnt[id]) {
		return ;
	} else if (w == sz + 1) {
		if (cur == cnt[id]) {
			memcpy(fa_tmp, fa, sizeof(fa));
			int i; for (i=1;i<=sz;i++) if (vis[i]) {
				if (find(que[id][i-1].u) == find(que[id][i-1].v)) break;
				fa[find(que[id][i-1].u)] = find(que[id][i-1].v);
			}	
			tmp += (i == sz + 1);
			memcpy(fa, fa_tmp, sizeof(fa));
		}
	} else {
		DFS(w+1, sz, cur, id, tmp);
		vis[w] = 1;
		DFS(w+1, sz, cur+1, id, tmp);
		vis[w] = 0;
	}
}

int main(){
	n = read(); m = read();
	for (int i=1,u,v;i<=m;i++) {
		e[i].u = u = read(); 
		e[i].v = v = read();
		_hash[i] = e[i].w = read();
	}
	sort(_hash+1, _hash+1+m);
	tot = unique(_hash+1, _hash+1+m) - _hash - 1;
	for (int i=1,tmp;i<=m;i++) {
		tmp = lower_bound(_hash+1, _hash+1+tot, e[i].w) - _hash;
		que[tmp].push_back(e[i]);
	}
	for (int i=1;i<=n;i++)
		fa[i] = i;
	for (int i=1;i<=tot;i++) {
		for (int j=que[i].size()-1;~j;j--) {
			if (find(que[i][j].u) != find(que[i][j].v)) {
				fa[find(que[i][j].u)] = find(que[i][j].v);
				cnt[i]++;
			}
		}
	} 
	for (int i=2;i<=n;i++) {
		if (find(i) != find(1)) {
			puts("0");
			exit(0);
		}
	}
	
	for (int i=1;i<=n;i++) 
		fa[i] = i;
	for (int i=1,tmp=0;i<=tot;i++,tmp=0) if (cnt[i]) {
		DFS(1,que[i].size(),0,i,tmp);
		for (int j=que[i].size()-1;~j;j--) 
			fa[find(que[i][j].u)] = find(que[i][j].v);
		(vout *= tmp) %= MOD;
	}
	printf("%d\n",vout);
	return 0;
}

【BZOJ 3943】[Usaco2015 Feb] SuperBull

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3943
离线版题目:http://paste.ubuntu.com/23080229/

XOR意义下的位运算生成树

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int N = 2000+9;
const int M = N*32;
const int SGZ = 2;

int n,arr[N],fa[N],to[N],val[N];
LL vout;

namespace Trie{
	int MX[M],MN[M],ch[M][SGZ],cnt,root,NUM,COL,ans_tmp;
	
	inline void init(){
		memset(MX,-1,sizeof(MX));
		memset(MN,-1,sizeof(MN));
		memset(ch,0,sizeof(ch));
		cnt = root = 0;
	}
	
	void Insert(int &w, int t){
		if (!w) w = ++cnt; 
		if (!~MX[w] || MX[w] < COL) MX[w] = COL;
		if (!~MN[w] || MN[w] > COL) MN[w] = COL;
		if (t) Insert(ch[w][(NUM&t)>0],t>>1);  
	}
	
	inline void insert(int num, int col){
		if (!root) root = ++cnt;
		NUM = num, COL = col;
		Insert(ch[root][(num&(1<<30))>0],1<<29);
	}
	
	void Query(int w, int t){
		if (t) {
			int to = ch[w][((NUM&t)>0)^1];
			if (to && (MX[to] != COL || MN[to] != COL)) ans_tmp |= t, Query(to,t>>1);
			else Query(ch[w][(NUM&t)>0],t>>1);
 		} else {
			if (COL != MN[w]) COL = MN[w];
			else COL = MX[w]; 	
		}
	} 
	
	inline pair<int,int> query(int num, int col){
		ans_tmp = 0; NUM = num; COL = col;
		Query(root,1<<30);
		return make_pair(ans_tmp,COL);
	}
};

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
	return f;
}

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret; 
}

int main(){
	n = read(); int cnt = n-1;
	for (int i=1;i<=n;i++) arr[i] = read(), fa[i] = i;
	while (cnt) {
		Trie::init(); 
		memset(val,0,sizeof(val));
		for (int i=1;i<=n;i++) Trie::insert(arr[i],find(i));
		for (int i=1;i<=n;i++) {
			pair<int,int> tmp = Trie::query(arr[i],fa[i]);
			if (tmp.first > val[fa[i]]) val[fa[i]] = tmp.first, to[fa[i]] = tmp.second;
		}
		for (int i=1;i<=n;i++) if (to[i] && find(to[i]) != find(i)) 
			vout += val[i], fa[find(i)] = find(to[i]), cnt--;
	}
	printf("%lld\n",vout);
	return 0;
}

不过貌似这个题直接暴力就行了?

【UOJ 176】新年的繁荣

题目传送门:http://uoj.ac/problem/176

位运算生成树系列之&最大
详细情况,见之后的算法笔记吧

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int N = 1<<19;

int n,m,num[N],fa[N];
LL vout;

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

inline int find(int w){
	int f=fa[w],tmp;
	while (f != fa[f]) f = fa[f];
	while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
	return f;
}

int main(){
	n = read(); m = read();
	for (int i=1,v;i<=n;i++) 
		if (num[v=read()]) vout += v;
		else num[v] = v;
	for (int q=(1<<m)-1;q;q--) { fa[q] = q;
		for (int i=1;i<=m && !num[q];i++) num[q] = num[q|1<<i-1];
		for (int i=1,f1,f2,u=num[q],v;i<=m;i++) 
			if ((v=num[q|1<<i-1]) && find(u) != find(v)) vout += q, fa[find(u)] = find(v);
	}
	printf("%lld\n",vout);
	return 0;
}

来补一个Boruvka + trie的版本:

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define R(x) ((x)>0)
using namespace std;

const int N = 100000+9;
const int M = N*32*4;

int n,arr[N],v[N],sur[N],fa[N],m;
LL vout = 0;

namespace Trie{
	int root,ch[M][2],MX[M],MN[M],cnt,NUM,COL,ans_tmp;
	
	inline void init(){
		memset(ch,0,sizeof(ch));
		memset(MX,0,sizeof(MX));
		memset(MN,0,sizeof(MN));
		cnt = root = 1;
	}
	
	void Insert(int &w, int t){
		if (!w) w = ++cnt;
		if (!MX[w] || MX[w] < COL) MX[w] = COL;
		if (!MN[w] || MN[w] > COL) MN[w] = COL;
		if (t) Insert(ch[w][R(NUM&t)],t>>1);
	}
	
	inline void insert(int num, int col){
		NUM = num; COL = col;
		Insert(ch[root][R(num&(1<<m))],1<<m-1);
	}
	
	void Merge(int &w, int p){
		if (!w) w = ++cnt;
		if (!MX[w] || MX[w] < MX[p]) MX[w] = MX[p];
		if (!MN[w] || MN[w] > MN[p]) MN[w] = MN[p];
		
		if (ch[p][0]) Merge(ch[w][0], ch[p][0]);
		if (ch[p][1]) Merge(ch[w][1], ch[p][1]);
	}
	
	void merge(int w){
		if (ch[w][1]) Merge(ch[w][0],ch[w][1]), merge(ch[w][1]);
		if (ch[w][0]) merge(ch[w][0]); 
	}
	
	void Query(int w, int t){
		if (t) {
			if (R(NUM&t) && (MN[ch[w][1]] != COL || MX[ch[w][1]] != COL)) ans_tmp|=t, Query(ch[w][1], t>>1); 
			else Query(ch[w][0],t>>1);
		} else {
			if (MN[w] != COL) COL = MN[w];
			else COL = MX[w];
		}
	}
	
	inline pair<int,int> query(int num, int col){
		ans_tmp = 0; NUM = num, COL = col;
		Query(root,1<<m);
		return make_pair(ans_tmp,COL);
	}
};

inline int find(int w){
	int f=fa[w], tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
	return f;
}

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

int main(){
	n = read(); m = read(); int cnt = n-1;
	for (int i=1;i<=n;i++) fa[i] = i, arr[i] = read();
	while (cnt) {
		Trie::init(); memset(v,-1,sizeof(v));
		for (int i=1;i<=n;i++) Trie::insert(arr[i],find(i));
		Trie::merge(Trie::root);
		for (int i=1;i<=n;i++) {
			pair<int,int> tmp = Trie::query(arr[i],fa[i]);
			if (tmp.first > v[fa[i]]) v[fa[i]] = tmp.first, sur[fa[i]] = tmp.second;
		}
		for (int i=1;i<=n;i++) if (~v[i] && find(i) != find(sur[i])) 
			vout += v[i], fa[find(i)] = find(sur[i]), cnt--;
	}
	printf("%lld\n",vout);
	return 0;
}

【POJ 3522】Slim Span

题目传送门:http://poj.org/problem?id=3522

今天在水位运算生成树,无聊来水一水
很暴力,枚举最大边,然后搞一搞,并查集判树

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 100+9;
const int M = 10000+9;
const int INF = 1000000000;

struct Edge{int u,v,w;}e[M];
int n,m,vout,fa[N];

inline bool operator < (const Edge &A, const Edge &B) {return A.w < B.w;}

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w], fa[w]=f, w=tmp;
	return f;
}

inline int Get_Ans(int lim){
	for (int i=1;i<=n;i++) fa[i] = i;
	fa[e[lim].u] = fa[e[lim].v];
	for (int i=lim-1,t=n-2,f1,f2;i;i--) {
		f1 = find(e[i].u); f2 = find(e[i].v);
		if (f1 != f2) fa[f2] = f1, t--;
		if (!t) return e[i].w;
	}
	return -INF;
}

int main(){
	while (scanf("%d%d",&n,&m) && (n||m)) {
		for (int i=1;i<=m;i++) e[i].u = read(), e[i].v = read(), e[i].w = read();
		sort(e+1,e+1+m); vout = INF;
		for (int lim=m;lim>=n-1;lim--) 
			vout = min(vout, e[lim].w - Get_Ans(lim));
		if (n <= 2) printf("0\n");
		else printf("%d\n",vout>=INF?-1:vout);	
	}
	return 0;
}

【BZOJ 2429】[HAOI2006] 聪明的猴子

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2429

MST的板题,MST搞出来,再拿每一个猴子比一比就好
好吧,其实我是来练Boruvka的……

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define pow(x) ((x)*(x))
using namespace std;

const int N = 1000+9;
const int M = 1000000+9;
const double EPS = 1e-8;

int X[N],Y[N],to[M],nxt[M],head[N],val[N],tot,n,m,vout,fa[N],cot[N];
double w[M],cpt[N],MX;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void AddEdge(int i, int j){
	double tmp = sqrt(pow(X[i]-X[j])+pow(Y[i]-Y[j]));
	to[++m] = j; nxt[m] = head[i]; w[m] = tmp; head[i] = m;
	to[++m] = i; nxt[m] = head[j]; w[m] = tmp; head[j] = m;
}

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
	return f;
}

inline void Boruvka(){
	for (int i=1;i<=n;i++) fa[i] = i;
	for (int t=n;t>1;) {
		memset(cot,0,sizeof(cot));
		for (int i=1,f1,f2;i<=n;i++) for (int j=head[i];j;j=nxt[j]){
			f1 = find(i); f2 = find(to[j]);
			if (f1 != f2) {
				if (!cot[f1] || cpt[f1] > w[j]) cot[f1] = f2, cpt[f1] = w[j];
				if (!cot[f2] || cpt[f2] > w[j]) cot[f2] = f1, cpt[f2] = w[j];
			} 	
		}
		
		for (int i=1,ft;i<=n;i++) if (fa[i] == i) {
			if ((ft = find(cot[i])) != i) {
				fa[ft] = i; MX = max(MX, cpt[i]); t--;
			}
		} 
	}
}

int main(){
	tot=read(); for (int i=1;i<=tot;i++) val[i] = read();
	n = read(); for (int i=1;i<=n;i++) {
		X[i] = read(); Y[i] = read();
		for (int j=1;j<i;j++) AddEdge(i,j);
	}
	Boruvka();
	for (int i=1;i<=tot;i++) if (EPS+val[i] >= MX) vout++;
	printf("%d\n",vout);
	return 0;
}

【模板库】Borůvka’s algorithm

参考例题:http://www.lydsy.com/JudgeOnline/problem.php?id=2429
参考代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define pow(x) ((x)*(x))
using namespace std;

const int N = 1000+9;
const int M = 1000000+9;
const double EPS = 1e-8;

int X[N],Y[N],to[M],nxt[M],head[N],val[N],tot,n,m,vout,fa[N],cot[N];
double w[M],cpt[N],MX;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void AddEdge(int i, int j){
	double tmp = sqrt(pow(X[i]-X[j])+pow(Y[i]-Y[j]));
	to[++m] = j; nxt[m] = head[i]; w[m] = tmp; head[i] = m;
	to[++m] = i; nxt[m] = head[j]; w[m] = tmp; head[j] = m;
}

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
	return f;
}

inline void Boruvka(){
	for (int i=1;i<=n;i++) fa[i] = i;
	for (int t=n;t>1;) {
		memset(cot,0,sizeof(cot));
		for (int i=1,f1,f2;i<=n;i++) for (int j=head[i];j;j=nxt[j]){
			f1 = find(i); f2 = find(to[j]);
			if (f1 != f2) {
				if (!cot[f1] || cpt[f1] > w[j]) cot[f1] = f2, cpt[f1] = w[j];
				if (!cot[f2] || cpt[f2] > w[j]) cot[f2] = f1, cpt[f2] = w[j];
			} 	
		}
		
		for (int i=1,ft;i<=n;i++) if (fa[i] == i) {
			if ((ft = find(cot[i])) != i) {
				fa[ft] = i; MX = max(MX, cpt[i]); t--;
			}
		} 
	}
}

int main(){
	tot=read(); for (int i=1;i<=tot;i++) val[i] = read();
	n = read(); for (int i=1;i<=n;i++) {
		X[i] = read(); Y[i] = read();
		for (int j=1;j<i;j++) AddEdge(i,j);
	}
	Boruvka();
	for (int i=1;i<=tot;i++) if (EPS+val[i] >= MX) vout++;
	printf("%d\n",vout);
	return 0;
}

算法简介:https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm
算法正确性证明:http://oi.cyo.ng/wp-content/uploads/2016/08/02345678641.png
国外带注释模板:http://www.geeksforgeeks.org/greedy-algorithms-set-9-boruvkas-algorithm/