无线广播(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
恶心死我的一道题:瞎写写算了
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; } |