bzoj2429- 聪明的猴子

题意其实就是说有很多个点，求一组边把它们都连接起来，并且最大的那条边最小。很明显这就是一个最小生成树，是一颗保证最长边最短的树。

代码

刚刚学了个Borůvka算法，于是写了两个。

Borůvka

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

#include<cmath>

#define Pow(x) ((x)*(x))

using namespace std;

int read() {

	int x=0,f=1;

	char c=getchar();

	for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;

	for (;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*f;

}

const int maxh=505;

const int maxn=1e3+10;

const int maxm=maxn*maxn;

int jp[maxh],n,m,all,f[maxn],close[maxn];

struct node {

	double x,y;

} a[maxn];

struct bian {

	int u,v;

	double w;

} e[maxm];

double dist(node &a,node &b) {

	return sqrt(Pow(a.x-b.x)+Pow(a.y-b.y));

}

int find(int x) {

	return f[x]==x?x:f[x]=find(f[x]);

}

double boruvka() {

	for (int i=1;i<=n;++i) f[i]=i;

	e[0].w=1e300;

	double ret=0;

	for (int t=n;t>1;) {

		memset(close,0,sizeof close);

		for (int i=1;i<=all;++i) if (find(e[i].u)!=find(e[i].v)) {

			int fx=find(e[i].u),fy=find(e[i].v);

			if (e[i].w<e[close[fx]].w) close[fx]=i;

			if (e[i].w<e[close[fy]].w) close[fy]=i;

		}

		for (int i=1;i<=n;++i) if (find(i)==i && close[i]) {

			int x=find(e[close[i]].u),y=find(e[close[i]].v);

			if (x!=y) f[x]=y,ret=max(ret,e[close[i]].w),--t;

		}

	}

	return ret;

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

	freopen("my.out","w",stdout);

#endif

	m=read();

	for (int i=1;i<=m;++i) jp[i]=read();

	n=read(),all=0;

	for (int i=1;i<=n;++i) a[i].x=read(),a[i].y=read();

	for (int i=1;i<=n;++i) for (int j=i+1;j<=n;++j) e[++all]=(bian){i,j,dist(a[i],a[j])};

	double mst=boruvka();

	int ans=0;

	for (int i=1;i<=m;++i) ans+=(jp[i]>=mst);

	printf("%d\n",ans);

	return 0;

}

Kruskal

#include<cstdio>

#include<cctype>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

const int maxh=505;

const int maxn=1e3+10;

const int maxm=maxn*maxn;

struct bian {

	int u,v;

	double w;

	inline bool operator < (const bian &a) const {return w<a.w;}

} e[maxm];

struct P {

	double x,y;

} a[maxn];

double jp[maxn];

int f[maxn];

int find(int x) {

	return f[x]==x?f[x]:f[x]=find(f[x]);

}

double dist(P &a,P &b) {

	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("test.in","r",stdin);

	freopen("std.out","w",stdout);

#endif

	int n,m;

	scanf("%d",&m);

	for (int i=1;i<=m;++i) scanf("%lf",jp+i);

	scanf("%d",&n);

	for (int i=1;i<=n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);

	int all=0;

	double mst=0;

	for (int i=1;i<=n;++i) for (int j=i+1;j<=n;++j) e[++all]=(bian){i,j,dist(a[i],a[j])};

	sort(e+1,e+all+1);

	for (int i=1;i<=n;++i) f[i]=i;

	for (int i=1,j=0;i<=all && j<n;++i) {

		int u=e[i].u,v=e[i].v,fx=find(u),fy=find(v);

		double w=e[i].w;

		if (fx!=fy) {

			f[fx]=fy;

			mst=max(mst,w);

			++j;

		}

	}

	int ans=0;

	for (int i=1;i<=m;++i) if (jp[i]>=mst) ++ans;

	printf("%d\n",ans);

	return 0;

}