描述 某广播公司要在一个地区架设无线广播发射装置。该地区共有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.用C语言编写
时间: 2024-03-01 08:51:13 浏览: 215
以下是用C语言实现的代码,时间复杂度为O(n^2):
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 1000
int n, m;
int map[MAX_N + 1][MAX_N + 1];
int color[MAX_N + 1];
int main()
{
int i, j, k, flag;
scanf("%d %d", &n, &m);
memset(map, 0, sizeof(map));
for (i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
map[u][v] = map[v][u] = 1;
}
memset(color, 0, sizeof(color));
for (i = 1; i <= n; i++) {
flag = 1;
for (j = 1; j <= n; j++) {
if (map[i][j] && color[i] == color[j]) {
flag = 0;
break;
}
}
if (flag) {
color[i] = 1;
} else {
color[i] = 2;
}
}
for (i = 1; i <= n; i++) {
for (j = i + 1; j <= n; j++) {
if (map[i][j] && color[i] == color[j]) {
printf("-1\n");
return 0;
}
}
}
printf("1\n");
return 0;
}
```
该代码使用了邻接矩阵来存储小镇之间的关系,使用了一个一维数组来保存每个小镇的颜色,其中颜色1表示使用FM104.2波段,颜色2表示使用FM98.6波段。在遍历每个小镇时,判断它与邻居节点之间的关系,如果邻居节点已经选择了某个波段,则将当前小镇的该波段选择情况设为相反的颜色。如果无法满足要求,则输出-1,否则输出1。
阅读全文