Beyond the Void
BYVoid
USACO DEC07 Silver Building Roads 建造路径

求包含给定的M条边的最小生成树。

可以用Kruskal算法加并查集,再读入M条边的时候先把这些边加入树中,再把最小的不构成环的N(N-1)/2-1-M条边加入树,算出边权和。

//最小生成树 Kruskal + 并查集
#include <iostream>
#include <cmath>
#define MAX 1001
using namespace std;
 
class tUFS
{
private:
	int F[MAX],Size;
	int findroot(int a)
	{
		int b=a,t;
		while (F[a]>0)
			a=F[a];
		while (F[b]>0)
		{
			t=F[b];
			F[b]=a;
			b=t;
		}
		return a;
	}
public:
	bool judge(int a,int b)
	{
		return F[findroot(a)]==F[findroot(b)];
	}
	void merge(int a,int b)
	{
		F[findroot(b)]=findroot(a);
	}
	tUFS(int N)
	{
		Size=N;
		for (int i=1;i<=N;i++)
			F[i]=-i;
	}
};
 
typedef struct
{
	int a,b;
	double v;
}edge;
 
typedef struct
{
	int x,y;
}point;
 
tUFS *U;
int N,M,C;
double Ans;
edge E[MAX*MAX];
point P[MAX];
 
void quicksort(int i,int j)
{
	int t1=i,t2=j;
	edge T,k=E[(i+j)/2];
	do
	{
		while (E[t1].v<k.v) t1++;
		while (E[t2].v>k.v) t2--;
		if (t1<=t2)
		{
			T=E[t1];
			E[t1]=E[t2];
			E[t2]=T;
 
			t1++;
			t2--;
		}
	}while (t1<t2);
	if (t2>i) quicksort(i,t2);
	if (t1<j) quicksort(t1,j);
}
 
inline double dist(point a,point b)
{
	return sqrt ( (double)(a.x-b.x)*(a.x-b.x) + (double)(a.y-b.y)*(a.y-b.y) );
}
 
void init()
{
	int i,j,a,b;
	freopen("roads.in","r",stdin);
	freopen("roads.out","w",stdout);
	scanf("%d%d",&N,&M);
	U=new tUFS(N);
	for (i=1;i<=N;i++)
		scanf("%d%d",&P[i].x,&P[i].y);
	for (i=1;i<=M;i++)
	{
		scanf("%d%d",&a,&b);
		if (!U->judge(a,b))
			U->merge(a,b);
	}
	for (i=C=1;i<=N-1;i++)
	{
		for (j=i+1;j<=N;j++,C++)
		{
			if (C==62375)
				C=C;
			E[C].a=i;
			E[C].b=j;
			E[C].v=dist(P[i],P[j]);
		}
	}
	C--;
	quicksort(1,C);
}
 
void kruskal()
{
	int i,cnt;
	for (i=1,cnt=0;i<=C && cnt<C-1-M;i++)
	{
		if (!U->judge(E[i].a,E[i].b))
		{
			U->merge(E[i].a,E[i].b);
			Ans+=E[i].v;
			cnt++;
		}
	}
}
 
int main()
{
	init();
	kruskal();
	printf("%.2lfn",Ans);
	return 0;
}
<a href="http://www.ruvtex.cn/wiki/USACOMonthly/2007_12_S/Building_Roads/Chinese">建造路径</a>

译 by CmYkRgB123

描述

Farmer John 刚刚得到了几个新农场!他想把这几个农场用路连接起来,这样他就可以通过笔直的公路从一个农场到另一个农场了。现在已经有了几条连接着的农场。

N (1 ≤ N ≤ 1,000) 个农场中,每个农场的位置在坐标平面的 (Xi, Yi) (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000)。已经有 M (1 ≤ M ≤ 1,000) 条路以前就被建好了。请你帮助 Farmer John 考虑建设尽量少长度的额外的路,使他的农场连在一起。

输入

    * 第 1 行: 两个整数: N , M
    * 第 2..N+1 行: 两个整数 Xi , Yi
    * 第 N+2..N+M+2 行: 两个整数: i , j, 表示已经存在从农场i到农场j的路。 

输出

    * 第 1 行: 额外的路的最少长度,保留2小数。 请使用 64 位的浮点数。 

样例输入

4 1
1 1
3 1
2 3
4 3
1 4

样例输出

4.00

上次修改时间 2017-02-03

相关日志