这道题中若能够构成互不干扰的区域，其构成的图其实就是汉密尔顿路（Hamilton road），因此如果能够观察出来可以直接转化为汉密尔顿路的存在性证明，即便不能观察，我相信ACMer也能转化为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

---

　　本题将一对距离小于20Km的小镇 模拟为 一对无向边结点，这样就可以生成一个多连通(不一定)无向图，原问题要求这一对小镇不能够放置同种频率的Broadcast，因此可以将问题比对树的层次遍历问题——父结点和子结点的数据不能相同，可化为图的广度优先搜索问题——结点和其邻接点的数据不能相同(利用BFS一层一层向外拓展并标记，找到一对邻接点数据相同则返回false，全部标记成功则返回true)。

　　具体而言：将任意一点作为源点入队(标记为1)，向外将其所有邻接点入队(标记为-1),再将源点出队，再取队首点所有邻接点入队(标记为1),此判断有无邻接点为与队首同标记,有则返回false，没有则继续...

具体如下：

　　

 //邻接表+BFS-类似汉密尔顿路的存在证明

 //这里用1标记源点，-1标记邻接点，1标记邻接点的邻接点，以此类推。(没有矛盾则存在)

 //Time:39Ms  Memory:13760Kb(No.8)

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 using namespace std;

 #define MAX 10005

 int n, m;        //小镇数-相距20Km内小镇对数

 int queue[MAX],head,tail;    //模拟队列-队首-队尾

 int cover;    //Broadcast放置数量

 //nextTown

 struct Node{

     int num;

     Node *next;

     Node(){ next = NULL; }

     Node(int n, Node *nn) :num(n), next(nn){}

 };

 //小镇

 struct Town{

     int state;    //状态

     Node *nt;    //nextTown

     Town(){ state = ; nt = NULL;}

     void insert(int num);

 }town[MAX];

 /*插入新边*/

 void Town::insert(int num)

 {

     if (this->nt == NULL)

         this->nt = new Node(num,NULL);

     else this->nt = new Node(num,this->nt);

 }

 bool BFS(int x)

 {

     queue[tail++] = x;

     town[x].state = ;

     cover++;    //No.x被cover

     while (head < tail)

     {

         Town cur = town[queue[head]];    //当前小镇

         Node *tmp = cur.nt;        //指向nextTown

         while (tmp != NULL)

         {

             if (!town[tmp->num].state){

                 town[tmp->num].state = -cur.state;    //cover不同Broadcast

                 cover++;        //No.(tmp->num)被cover

                 queue[tail++] = tmp->num;

             }

             else if (town[tmp->num].state == cur.state)    //被干扰

                 return false;

             tmp = tmp->next;

         }

         head++;

     }

     return true;

 }

 int main()

 {

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

     for (int i = ; i < m; i++)

     {

         int x, y;

         scanf("%d%d", &x, &y);    //d(x,y)<20Km

         town[x].insert(y);

         town[y].insert(x);

     }

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

     {

         if (!town[i].state)

         {

             if (BFS(i) == false)    //调用BFS-信号被干扰

             {

                 printf("-1\n");

                 return ;

             }

             if (cover == n)    //Place(放置)完毕

             {

                 printf("1\n");

                 return ;

             }

         }

     }

     return ;

 }

小墨= =原创

---

ACM/ICPC 之 数据结构-邻接表+BFS(TSH OJ-无线广播Broadcast)的相关教程结束。