閱讀428 返回首頁    go 阿裏雲 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 機房收費係統之全局認識