poj 3026 (最小生成树)

题意：起点开始有超过100个人，总共不会超过100个外星人，问把所有的外星人都搜出来花的最小时间。一条路径上的时间跟人数是无关的，只跟路径长度有关。

思路：刚开始人都在起点，当派一定人数去最近的外星人后，起点就变成两个了，然后从两个起点去最近的外星人，起点就变成三个了，，，，这就是最小生成树了。

include<stdio.h>

#include<math.h>

#include<queue>

#include<stdlib.h>

#include<string.h>

const int N=251;

const int inf=0x3fffffff;

using namespace std;

int num,f[N],n,m,k,map[51][51],dir[4][2]={0,1,0,-1,1,0,-1,0};

bool vis[51][51];

char cap[51][51];

struct edge

{

	int st,ed,w;

}e[N*N];

struct node

{

	int x,y;

}p[N];

void addedge(int x,int y,int w)

{

	e[num].st=x;e[num].ed=y;e[num++].w=w;

}

int dis(int i,int j)

{

	return abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);

}

int cmp(void const *a,void const *b)

{

	edge *c,*d;

	c=(edge *)a;

	d=(edge *)b;

	return c->w-d->w;

}

int find(int a)

{

	if(a!=f[a])

		f[a]=find(f[a]);

	return f[a];

}

void bfs(int u)

{

	queue<edge>Q;

	edge cur,next;

	int i,j,x,y;

	for(i=0;i<n;i++)

		for(j=0;j<m;j++)

		{

			map[i][j]=inf;

			vis[i][j]=false;

		}

	map[p[u].x][p[u].y]=0;vis[p[u].x][p[u].y]=true;

	cur.st=p[u].x;cur.ed=p[u].y,cur.w=0;

	Q.push(cur);

	while(!Q.empty())

	{

		cur=Q.front();

		Q.pop();vis[cur.st][cur.ed]=false;

		for(i=0;i<4;i++)

		{

			next.st=x=cur.st+dir[i][0];

			next.ed=y=cur.ed+dir[i][1];

			if(x>=0&&x<n&&y>=0&&y<m&&cap[x][y]!='#')

			{

				next.w=cur.w+1;

				if(map[x][y]>next.w)

				{

					map[x][y]=next.w;

					if(vis[x][y]==false)

					{Q.push(next);vis[x][y]=true;}

				}

			}

		}

	}

	for(i=1;i<k;i++)

	{

		if(i==u)continue;

		addedge(u,i,map[p[i].x][p[i].y]);

	}

}

int main()

{

	int i,j,t,sum,x,y;

	char str[100],ch;

	scanf("%d",&t);

	while(t--)

	{

		scanf("%d%d",&m,&n);

		ch=getchar();

		while(ch!='\n')

			ch=getchar();

		k=1;num=0;sum=0;

		for(i=0;i<n;i++)

		{

			gets(str);

			for(j=0;j<m;j++)

			{

				cap[i][j]=str[j];

				if(str[j]=='A'||str[j]=='S')

				{p[k].x=i;p[k++].y=j;}

			}

		}

		for(i=1;i<k;i++)

		{f[i]=i;bfs(i);}

		qsort(e,num,sizeof(e[0]),cmp);

		for(i=0;i<num;i++)

		{

			x=find(e[i].st);

			y=find(e[i].ed);

			if(x==y)continue;

			sum+=e[i].w;

			f[x]=find(y);

		}

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

	}

	return 0;

}

巴特西

poj 3026 (最小生成树)

最新文章

热门文章