[UVa] 10147 - Highways

題目網址:http://goo.gl/XmjPAE

題意:
給 n 個城市的座標位置，接著給 m 條已存在高速公路，每條相連兩座城市，問建總花費最少的高速公路，使得全部的城市都能互通。


解法: MST。

TAG: Minimum Spanning Tree

注意:

程式碼:

	/**
	* Tittle: 10147 - Highways
	* Author: Cheng-Shih, Wong
	* Date: 2015/04/09
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	#include <algorithm>
	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 N 800
	class Edge {
	public:
	int u, v;
	double d;
	Edge( int _u=0, int _v=0, double _d=0 ):
	u(_u), v(_v), d(_d) {}
	const bool operator<( const Edge &op ) const {
	return d < op.d;
	}
	};
	// declarations
	int t;
	int n, m;
	double x[N];
	double y[N];
	int s[N];
	int ecnt;
	Edge edge[N*N];
	// functions
	int findS( int p )
	{
	if( s[p] < 0 )
	return p;
	return s[p] = findS(s[p]);
	}
	void unionS( int p, int q )
	{
	p = findS(p);
	q = findS(q);
	if( p!=q )
	s[p] = q;
	}
	inline double dis( int a, int b )
	{
	return sqrt( (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]) );
	}
	// main function
	int main( void )
	{
	int u, v;
	int ans;
	// input
	scanf( "%d", &t );
	while( t-- ) {
	scanf( "%d", &n );
	FOR( i, 1, n ) scanf( "%lf%lf", &x[i], &y[i] );
	// solve & output
	clr( s, -1 );
	scanf( "%d", &m );
	FOR( i, 1, m ) {
	scanf( "%d%d", &u, &v );
	unionS( u, v );
	}
	ecnt = 0;
	FOR( i, 1, n ) FOR( j, i+1, n )
	edge[++ecnt] = Edge( i, j, dis(i,j) );
	sort( edge+1, edge+1+ecnt );
	ans = 0;
	FOR( i, 1, ecnt ) {
	u = edge[i].u;
	v = edge[i].v;
	// printf( "@ %d %d\n", u, v );
	if( findS(u) != findS(v) ) {
	unionS( u, v );
	printf( "%d %d\n", u, v );
	++ans;
	}
	}
	if( !ans )
	puts("No new highways need");
	if( t )
	putchar('\n');
	}
	return 0;
	}

view raw 10147 - Highways.cpp hosted with ❤ by GitHub