清华OJ广度优先搜索题目。
描述
某广播公司要在一个地区架设无线广播发射装置。该地区共有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
问题分析&解决方案
通过读题不难发现题目的要点有两个：第一，每个小镇都需要安装一台发射机；第二，相距20km以内的小镇不能使用相同频率的波段。我们要做的就是通过题目给出的距离小于20km的小镇列表，判断是否能够保证每个小镇都能正常收听广播。
因为相互距离小于20km的小镇之间才会发生干扰，所以我们只需要考虑这一部分小镇能否满足条件即可解决问题，而那些相隔较远的小镇在这个题目中对我们没有造成任何危害。
现在我们讨论距离小于20km的这一部分小镇，假设这一部分小镇队集合为M（可以直接理解为图）。题目已经明确指出，在距离小于20km的前提下，如两个小镇有相同的波段就会互相干扰，所以对于M中任意一个小镇队(u,v)，在u的频率确定的条件下，v的频率也随之固定。
因为我们对频率没有更多的附加条件，所以我们可以将FM104.2和FM98.6两个波段直接抽象为两个不同的标志，作为小镇的一个属性ele。之后我们在M内任意初始化其中一个节点的ele属性（初始化的值也是任意的，因为抽象只是为了区分两种情况），按照小镇队频率互斥的要求我们就可以把与之联通的所有小镇的ele属性确定下来。只要过程中不出现相互矛盾的点，我们就可以成功布置。
考虑到给出的M可能是分块的，所以在执行完一次扩展之后程序还需要对其他节点进行判断。这样就能够保证程序的正确性。
算法设计
现在回顾一下我们需要做的操作：按照互斥的规则从任意一点展开，判断是否能够蔓延到所有的节点。因为数据是成对输入的，所以我们很容易联想到用图来保存，那么我们在这个题目中所需要的操作实质上就变成了一个图遍历的问题，更准确来讲，BFS问题，因为广度优先更有利于提前发现不满足互斥条件的点。
所以实现思路也很明确了：用图的形式将输入数据保存下来，然后采用BFS策略对图进行遍历。考虑到要通过ele属性判断是否互斥，所以在定义图的节点的时候要加上这个属性，BFS中也要根据当前一轮搜索的出发点的属性设置与之相连的点的属性，或者判断已访问的点的属性是否和该轮搜索出发点的属性是否相同。
关于图的存储形式，我使用的是邻接表，采用邻接矩阵会耗费较大的空间。另外还要注意，本题中的图为无向图。而ele属性的三种标记形式，我有以下两种方案，我采用的是前者。
- 初始状态为0，相对立的两种状态为-1和1，可以直接通过取相反数的方法更新。
- 初始状态为2，相对立的两种状态为0和1，通过（x+1）%2的方式进行更新。
另外一点，本次题目因为要在清华OJ上进行测试，没有stl标准库，如果要用到队列的话需要自己实现。我采用了链表和数组模拟两种方式对队列进行了实现，均通过了测试，代码将在下面给出。另外也一并附上stl版本。
编程实现
用链表实现队列
#include <iostream>
//#include <queue>
using namespace std;
//队列节点
struct node_of_queue{
int del;
node_of_queue* next;
node_of_queue(int v, node_of_queue* x = NULL):del(v),next(x){}
};
//队列类
class myQueue{
public:
node_of_queue* front;
node_of_queue* back;
myQueue():front(NULL),back(NULL){}
int Front(){
if(front)
return (front->del);
return 0;
}
void push(int x){
node_of_queue* tmp = new node_of_queue(x);
if(!front)
front = tmp;
if(!back)
back = tmp;
else{
back->next = tmp;
back = tmp;
}
return ;
}
bool empty(){
return front == NULL;
}
void pop(){
if(front){
node_of_queue* tmp = front;
front = front->next;
if(!front)
back = NULL;
delete tmp;
}
return ;
}
};
//小镇节点
struct Node{
int _id;
Node* _next;
Node(int id, Node* next = NULL):_id(id), _next(next){}
};
//小镇集合
struct Nodes{
int _ele;
Node* _next;
Nodes():_ele(0), _next(NULL){}
void insert(int id);
};
void Nodes::insert(int id){
_next = new Node(id, _next);
return ;
}
int main(){
Nodes nodes[10005];
myQueue myQ;
int n, m;
int v, u;
cin >> n >> m;
while(m--){
cin >> v >> u;
nodes[v].insert(u);
nodes[u].insert(v); //无向图需要两次插入
}
for(int cur = 1; cur <= n; cur++){
if(!nodes[cur]._ele){
nodes[cur]._ele = 1; //进行标记
myQ.push(cur);
int tmp;
while(!myQ.empty()){
tmp = myQ.Front();
myQ.pop();
Node* cur_node = nodes[tmp]._next;
while(cur_node){
if (nodes[cur_node->_id]._ele == nodes[tmp]._ele){
//已放置同色
cout << -1 << endl;
return 0;
}
if(!nodes[cur_node->_id]._ele){
//未放置
nodes[cur_node->_id]._ele = -nodes[tmp]._ele;
myQ.push(cur_node->_id); //只入队没被访问过的点
}
cur_node = cur_node ->_next;
}
}
}
}
cout << 1 << endl;
return 0;
}
用数组模拟队列
#include <iostream>
//#include <queue>
using namespace std;
int myQ[10005], front, back; //队列数组
struct Node{
int _id;
Node* _next;
Node(int id, Node* next = NULL):_id(id), _next(next){}
};
struct Nodes{
int _ele;
Node* _next;
Nodes():_ele(0), _next(NULL){}
void insert(int id);
};
void Nodes::insert(int id){
_next = new Node(id, _next);
return ;
}
int main(){
Nodes nodes[10005];
//queue<int> myQ;
int n, m;
int v, u;
cin >> n >> m;
while(m--){
cin >> v >> u;
nodes[v].insert(u);
nodes[u].insert(v);
}
for(int cur = 1; cur <= n; cur++){
if(!nodes[cur]._ele){
nodes[cur]._ele = 1; //进行标记
front = back = 0;
myQ[back++] = cur;
int tmp;
while(front < back){
tmp = myQ[front++];
Node* cur_node = nodes[tmp]._next;
while(cur_node){
if(!nodes[cur_node->_id]._ele){
//未放置
nodes[cur_node->_id]._ele = -nodes[tmp]._ele;
myQ[back++] = cur_node->_id;
}
else if (nodes[cur_node->_id]._ele == nodes[tmp]._ele){
//已放置同色
cout << -1 << endl;
return 0;
}
cur_node = cur_node ->_next;
}
}
}
}
cout << 1 << endl;
return 0;
}
stl标准模板库
#include <iostream>
#include <queue>
using namespace std;
struct Node{
int _id;
Node* _next;
Node(int id, Node* next = NULL):_id(id), _next(next){}
};
struct Nodes{
int _ele;
Node* _next;
Nodes():_ele(2), _next(NULL){}
void insert(int id);
};
void Nodes::insert(int id){
_next = new Node(id, _next);
return ;
}
int main(){
Nodes nodes[100];
queue<int> myQ;
int n, m;
int v, u;
cin >> n >> m;
while(m--){
cin >> v >> u;
nodes[v].insert(u);
nodes[u].insert(v);
}
int s = 1;
int cur = s;
do
if(nodes[cur]._ele == 2){
nodes[cur]._ele = (nodes[cur]._ele+1)%2; //进行标记
myQ.push(cur);
int tmp = cur;
while(!myQ.empty()){
tmp = myQ.front();
myQ.pop();
Node* cur_node = nodes[tmp]._next;
while(cur_node){
if(nodes[cur_node->_id]._ele == 2){
//未放置
nodes[cur_node->_id]._ele = (nodes[tmp]._ele+1)%2;
myQ.push(cur_node->_id);
}
else if (nodes[cur_node->_id]._ele == nodes[tmp]._ele){
//以放置同色
cout << -1 << endl;
return 0;
}
cur_node = cur_node ->_next;
}
}
}
while(s != (cur = (++cur%n)));
cout << 1 << endl;
return 0;
}
结果分析
最开始的代码使用的标准模板库中的queue，但是提交发现不能编译，于是自己手写了一个队列进行提交，但是只通过了7个测试。第一反应是自己的队列写错了，但经过多组数据测试之后发现是BFS过程中对已经访问过的点进行了入队操作。改正之后成功提交。之后顺便写了用数组模拟队列的代码，也成功通过。
总结体会
实现邻接表的时候发现自己对图的掌握程度相对较低，整个逻辑想了一会才能用代码写出来。这个程序一开始保存图的时候还保存成了有向图…
BFS搜索策略也是最近才接触，本以为上课的时候已经理解，但自己的代码写出来就有一些漏洞，这不是细节处理不到位，而是对这个概念理解的还不够清晰，不然怎么写都不会写错，即使写错了也能很快找出来。
算法不能只停在纸面上，还要落实到代码中。经过了这次编程任务，我觉得我对图、图搜索相关知识的理解又加深了一些。（至少BFS记的更清楚了🙃
另外感觉这次写的代码可读性不是很高📌