数据结构 邓俊辉 PA#3 无线广播(Broadcast) 题解

无线广播(Broadcast)


描述

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

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

输入

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

输出

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

输入样例

1
2
3
4
4 3
1 2
1 3
2 4

输出样例

1
1

限制

1 ≤ n ≤ 10000

1 ≤ m ≤ 30000

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

时间:2 sec

空间:256MB

提示

BFS

恶心死我的一道题:瞎写写算了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<cstdio>
#include<cstring>
using namespace std;
int u[30001],v[30001],next_[30001],first[10001];
int n,m;
bool visited[10001];
bool inqueue[10001];
int type[10001];
template <typename T> struct Queue{ //数组循环队列  
    private:
        int _capacity;
        int _size;
        int _front;
        int _rear;//real _rear+1;
        T * array;
        void enlargeCapacity(){
            T * new_arr=new T[_capacity*2];
            int cnter=0;
            for(int i=_front;i!=_rear;i=(i+1)%_capacity){
                new_arr[cnter++]=array[i];
            }
            _front=0;
            _rear=cnter;
            delete []array;
            array=new_arr;
        }
    public:
        Queue(){
            array=new T[500];
            _capacity=500;
            _size=0;
            _front=0;
            _rear=0;
        }
        ~Queue(){
            delete []array;
        }
        void push(T value){
            _size++;
            array[_rear]=value;
            _rear=(_rear+1)%_capacity;
            if(full())enlargeCapacity();
        }
        T & front(){
            return array[_front];
        }
        void pop(){
            _front=(_front+1)%_capacity;
            _size--;
        }
        bool empty(){
            return _size==0;
        }
        bool full(){
            return _size==_capacity;
        }
};
bool BFS(int start){
    Queue<int> queue;
    queue.push(start);
    type[start]=1;
    while(!queue.empty()){
        int node=queue.front();
        queue.pop();
        visited[node]=true;
        inqueue[node]=false;
        for(int e=first[node];e!=-1;e=next_[e]){
            if(!visited[v[e]]){
                if(type[node]==1){
                    if(type[v[e]]==1)return false;
                    type[v[e]]=2;
                }
                else{
                    if(type[v[e]]==2)return false;
                    type[v[e]]=1;
                }
                queue.push(v[e]);
                inqueue[v[e]]=true;
            }
        }
    }
}
int main(){
    memset(first,-1,sizeof(first));
    memset(visited,false,sizeof(visited));
    memset(inqueue,false,sizeof(inqueue));
    memset(type,-1,sizeof(type));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u[i],&v[i]);
        next_[i]=first[u[i]];
        first[u[i]]=i;
    }
    bool flag=true;
    for(int i=1;i<=n;i++){
        if(!visited[i]){
            flag=BFS(i);
            if(!flag){
                printf("-1");
                return 0;
            }
        }
    }
    printf("1");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注