UVa 10307 - Killing Aliens in Borg Maze

题目：在一个迷宫中，以S为起点，遇到A时可以分叉，问走到所有的A的路径和最小代价。

分析：图论，最短路，最小生成树。利用bfs求出所有的A和A以及A和S间的最短路，

            再在这个最短路生成的途中计算最小生成树即可。

注意：最多101个点，世界上最遥远的距离就是因为数组少开了1个而无限的WA( ⊙ o ⊙ )！

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <string>
#include <cstdio>

using namespace std;

string  maps[55];
int     smap[55][55];

typedef struct d_node
{
	int point1;
	int point2;
	int weight;
}enode;
enode edge[5555];

//union_set
int sets[105];
int rank[105];

void set_inital( int a, int b )
{
	for ( int i = a ; i <= b ; ++ i ) {
		rank[i] = 0;
		sets[i] = i;
	}
}

int  set_find( int a )
{
	if ( a != sets[a] )
		sets[a] = set_find( sets[a] );
	return sets[a];
}

void set_union( int a, int b )
{
	if ( rank[a] < rank[b] )
		sets[a] = b;
	else {
		if ( rank[a] == rank[b] )
			rank[a] ++;
		sets[b] = a;
	}
}
//end_union_set

int cmp_e( enode a, enode b )
{
	return a.weight < b.weight;
}

int kruskal( int n, int m )
{
	sort( edge, edge+m, cmp_e );
	
	set_inital( 0, n );
	int sum = 0;
	for ( int i = 0 ; i < m ; ++ i ) {
		int A = set_find( edge[i].point1 );
		int B = set_find( edge[i].point2 );
		if ( A != B ) { 
			set_union( A, B );
			sum += edge[i].weight+0LL;
		}
	}
	return sum;
}

typedef struct pnode
{
	int x,y,s;
	pnode( int X, int Y, int S ){x = X;y = Y;s = S;}
	pnode(){}
}point;
point Q[5005];
point V[105];

int  d[4][2] = {1,0,-1,0,0,1,0,-1};
void bfs( int s, int n, int m )
{
	for ( int i = 0 ; i < m ; ++ i )
	for ( int j = 0 ; j < n ; ++ j )
		smap[i][j] = 5005;
		
	int move = 0,save = 0;
	Q[save ++] = V[s];
	smap[V[s].x][V[s].y] = 0;
	while ( move < save ) {
		point New,now = Q[move ++];
		for ( int i = 0 ; i < 4 ; ++ i ) {
			New.x = now.x + d[i][0];
			New.y = now.y + d[i][1];
			New.s = now.s + 1;
			if ( New.x >= 0 && New.x < m && New.y >= 0 && New.y < n )
			if ( maps[New.x][New.y] != ‘#‘ && smap[New.x][New.y] > smap[now.x][now.y] + 1 ) {
				smap[New.x][New.y] = smap[now.x][now.y] + 1;
				Q[save ++] = New;
			}
		}
	}
}

int main()
{
	int t,n,m;
	while ( cin >> t )
	while ( t -- ) {
		cin >> n >> m;getchar();
		for ( int i = 0 ; i < m ; ++ i ) 
			getline( cin, maps[i] );
		
		int v_count = 0;
		for ( int i = 0 ; i < m ; ++ i )
		for ( int j = 0 ; j < n ; ++ j )
			if ( maps[i][j] == ‘S‘ || maps[i][j] == ‘A‘ )
				V[v_count ++] = point( i, j, 0 );
		
		int e_count = 0;
		for ( int i = 0 ; i < v_count ; ++ i ) {
			bfs( i, n, m );
			for ( int j = i+1 ; j < v_count ; ++ j ) {
				edge[e_count].point1 = i;
				edge[e_count].point2 = j; 
				edge[e_count].weight = smap[V[j].x][V[j].y];
				e_count ++;
			}
		}
		cout << kruskal( v_count, e_count ) << endl;
	}
	
	return 0;
}

UVa 10307 - Killing Aliens in Borg Maze,布布扣,bubuko.com

UVa 10307 - Killing Aliens in Borg Maze

原文：http://blog.csdn.net/mobius_strip/article/details/21905743