[UVa] 10397 - Connect the Campus

題意:
(from luckycat)


解法:
由 最小生成樹 Kruskal 演算法的概念延伸，從最小的邊開始找，若不形成迴圈就把邊加入，直到檢查完所有的邊。

注意:

程式碼:

	/**
	* Tittle: 10397 - Connect the Campus
	* Author: Cheng-Shih, Wong
	* Date: 2015/08/13
	*/
	// include files
	#include <bits/stdc++.h>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define F first
	#define S second
	#define PB push_back
	#define N 1000
	class Point {
	public:
	double x, y;
	Point( double _x=0, double _y=0 ):
	x(_x), y(_y) {}
	Point &read() {
	cin >> x >> y;
	return *this;
	}
	double dis( const Point &op ) const {
	return sqrt( (x-op.x)*(x-op.x)+(y-op.y)*(y-op.y) );
	}
	};
	class Edge {
	public:
	int u, v;
	double dis;
	Edge( int _u=0, int _v=0, double _d=0 ):
	u(_u), v(_v), dis(_d) {}
	const bool operator<( const Edge &op ) const {
	return dis < op.dis;
	}
	};
	typedef vector<Point> VP;
	typedef vector<Edge> VE;
	// declarations
	int n, m;
	VP buildings;
	VE connections;
	// functions
	int fat[N];
	int findSet( int p )
	{
	if( fat[p] < 0 ) return p;
	return (fat[p] = findSet(fat[p]));
	}
	void unionSet( int p, int q )
	{
	p = findSet( p );
	q = findSet( q );
	if( p!=q )
	fat[p] = q;
	}
	void init()
	{
	static int u, v;
	buildings.clear();
	buildings.PB( Point() );
	FOR( i, 1, n )
	buildings.PB( Point().read() );
	cin >> m;
	clr( fat, -1 );
	while( m-- ) {
	cin >> u >> v;
	unionSet( u, v );
	}
	connections.clear();
	FOR( i, 1, n ) FOR( j, i+1, n ) {
	connections.PB( Edge(i, j, buildings[i].dis( buildings[j] )) );
	}
	}
	void solve()
	{
	double ans = 0.0;
	sort( connections.begin(), connections.end() );
	for( Edge e : connections ) {
	if( findSet(e.u) != findSet(e.v) ) {
	ans += e.dis;
	unionSet(e.u,e.v);
	}
	}
	// output
	printf( "%.2lf\n", ans );
	}
	// main function
	int main( void )
	{
	// input
	while( cin >> n ) {
	init();
	solve();
	}
	return 0;
	}

view raw 10397 - Connect the Campus.cpp hosted with ❤ by GitHub