阅读428 返回首页    go 技术社区[云栖]

【Tsinghua】无线广播(broadcast)

一个BFS。


无线广播(broadcast)

描述

某广播公司要在一个地区架设无线广播发射装置。该地区共有n个小镇，每个小镇都要安装一台发射机并播放各自的节目。

不过，该公司只获得了FM104.2和FM98.6两个波段的授权，而使用同一波段的发射机会互相干扰。已知每台发射机的信号覆盖范围是以它为圆心，20km为半径的圆形区域，因此，如果距离小于20km的两个小镇使用同样的波段，那么它们就会由于波段干扰而无法正常收听节目。现在给出这些距离小于20km的小镇列表，试判断该公司能否使得整个地区的居民正常听到广播节目。

输入

第一行为两个整数n，m，分别为小镇的个数以及接下来小于20km的小镇对的数目。 接下来的m行，每行2个整数，表示两个小镇的距离小于20km（编号从1开始）。

输出

如果能够满足要求，输出1，否则输出-1。

输入样例 

4 3
1 2
1 3
2 4

输出样例 

1

限制

1 ≤ n ≤ 10000

1 ≤ m ≤ 30000

不需要考虑给定的20km小镇列表的空间特性，比如是否满足三角不等式，是否利用传递性可以推出更多的信息等等。

时间：2 sec

空间：256MB

提示

BFS


AC的代码：

#include <stdio.h>
#include <malloc.h>

int **map=NULL;
int *qUeue=NULL;
int *visited=NULL;
int head,tail;
int n,m;

//入队
void EnQueue(int data)
{
	//tail 始终指向一个空位
	qUeue[tail]=data;
	tail++;
}

//出队
void DeQueue()
{
	head++;
}

//判空
bool IsEmpty()
{
	if(head==tail)
		return true;
	return false;
}

//取队首（不出队）
int getFront()
{
	return qUeue[head];
}

//取第一个邻接点，有就返回第一个邻接点，否则返回-1
int GetFirstNeighbor(int v)
{
	int i;
	for(i=1;i<v;i++)
		if(map[v][i]==1)
			return i;

	for(i=v+1;i<=n;i++)
		if(map[i][v]==1)
			return i;
	return -1;
}

//取 (v,w) 的下一个邻接点，有就返回第一个邻接点，否则返回-1
int GetNextNeighbor(int v,int w)
{
	int i;
	if(w<v)
	{
		for(i=w+1;i<v;i++)
			if(map[v][i]==1)
				return i;

		for(i=v+1;i<=n;i++)
			if(map[i][v]==1)
				return i;
	}

	if(v<w)
	{
		for(i=w+1;i<=n;i++)
			if(map[i][v]==1)
				return i;
	}

	return -1;
}

//visited[i]==-1 表示安装了频段1，visited[i]==0 表示还没有安装广播，visited[i]==1 表示安装了频段2.
int bfs()
{
	head=tail=1;
	
	int v,w;
	v=1;
	visited[v]=1;
	EnQueue(v);  //将v进队
	while(IsEmpty()==false)
	{
		v=getFront();  //取队首元素至v（注意：不出队）
		w=GetFirstNeighbor(v);  //取v的第一个邻接点至w
		while(w!=-1)
		{
			if(visited[w] == visited[v])  return -1;
			if(visited[w] == 0)    {visited[w] = -visited[v];   EnQueue(w);}
			w=GetNextNeighbor(v, w);  //取下一个邻接点
		}
		DeQueue();  //出队
	}
	return 1;
}

int main()
{
	scanf("%d%d",&n,&m);
	int array=n+2;
	//动态申请二维数组
	map=(int **)malloc(sizeof(int *) * array);
	int i;
	for(i=1;i<array;i++)
		*(map+i)=(int *)malloc(sizeof(int) * i);

	//动态申请一维数组
	visited=(int *)malloc(array*sizeof(int));
	qUeue=(int *)malloc(array*sizeof(int));
	
	int a,b;
	int tmp;
	//保证a<=b，只记录邻接矩阵的一半
	for(i=0;i<m;i++)
	{
		scanf("%d%d",&a,&b);
		if(b>a)
		{
			tmp=a;
			a=b;
			b=tmp;
		}
		map[a][b]=1;
	}
	
	int result=bfs();
	printf("%d\n",result);
	
	return 0;
}





最后更新：2017-04-03 05:39:38

  上一篇：go 【Tsinghua】旅行商(TSP)
  下一篇：go 机房收费系统之全局认识