林厚从信息学奥赛课课通第7单元第6课队列的应用课件.pptVIP

“ ” “ ” 第7单元第6课 队列的应用 信息学奥赛培训之数据结构 例1、Blah数集(blah,1s,256MB) 数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对于以a为基的集合Ba定义如下：(1) a是集合Ba的基，且a是Ba的第一个元素；(2)如果x在集合Ba中，则2x+1和3x+1也都在集合Ba中；(3)没有其他元素在集合Ba中了。现在小高斯想知道如果将集合Ba中元素按照升序排列，第N个元素会是多少？注意：集合中没有重复的元素。输入格式：1行，两个正整数，分别表示集合的基a(1=a=50)以及所求元素序号n(1=n=1000000).输出格式：1行，1个正整数，表示集合Blah的第n个元素值.输入样例1：1 100输出样例1：418 输入样例2： 28 5437 输出样例2： 900585 问题分析： 根据条件，除了第一个数a以外，可以把数集q[]的所有数分成两个子集，一个是用2x+1来表示的数的集合1，另一个是用3x+1来表示的数的集合2，两个集合要保持有序非常容易，只需用两个指针two和three来记录。其中two表示集合1下一个要产生的数是由q[two]*2+1得到，three表示集合2下一个要产生的数是由q[three]*3+1得到。接下来比较q[two]*2+1和q[three]*3+1的大小关系： 1）如果q[two]*2+1q[three]*3+1，则把q[two]*2+1加入到数集中。 2）如果q[two]*2+1q[three]*3+1，则把q[three]*3+1加入到数集中。 3）如果q[two]*2+1＝q[three]*3+1，则取任意一个加入数集中即可。 所以，本题就是利用队列先进先去的特点，模拟n个数依次产生的过程。 例2、关系网络(relationship,1s,256MB) 问题描述： 有n个人，他们的编号为1~n，其中有一些人相互认识，现在x想要认识y，可以通过他所认识的人来认识更多的人（如果a认识b,b认识c,那么a可以通过b来认识c），求出x最少需要通过多少人才能认识y。 输入格式： 第1行3个整数n、x、y，2=n=100; 接下来的n行是一个n*n的邻接矩阵，a[i][j]=1表示i认识j,a[i][j]=0表示不认识。保证i=j时，a[i][j]=0,并且a[i][j]=a[j][i]。 输出格式： 1行，一个整数，表示x认识y最少需要通过的人数。数据保证x一定能认识y。 输入样例： 5 1 5 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0 输出样例： 2 问题分析： 本题是最优值问题。显然，如果x和y本身就认识，则答案是0；否则，答案至少为1.如果x和y通过z这一个人就间接认识，那么答案是1，可以通过穷举z来实现；否则，答案至少为2.……如此做下去，一定能找到答案（最大为n-2）.这种算法叫作“广度优先有哪些信誉好的足球投注网站”，简称“广搜”，具体实现需要通过一个队列在实现过程中扩展到所有人。 把x加入队列并设置为队首元素，设q[x][1]=0，从队首开始进行广搜，穷举邻接矩阵的第x行，看x认识谁（判断a[x][j]=1），认识的人(j)全部依次入队，并且q[j][1]++.如果出现了y，则输出q[f][1]-1，结束有哪些信誉好的足球投注网站；否则，取出队首元素继续广搜。 例3、图的广度优先遍历。(graph_bfs,1s,256MB) 问题描述： 读入一个用邻接矩阵存储的无向图，输出它的广度优先遍历序列。 输入格式： 第1行1个正整数n，表示图中顶点数,2=n=100; 接下来的n行是一个n*n的邻接矩阵，a[i][j]=1表示顶点i和顶点j之间有直接边相连， a[i][j]=0表示没有直接边相连。保证i=j时，a[i][j]=0,并且a[i][j]=a[j][i]。 输出格式： 输出1~n的某一排列，表示从顶点1开始，对该图进行广度优先遍历得到的顶点序列，每两个数之间用一个”-”分隔。 输入样例： 8 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 输出样例： 1-2-3-4-5-7-8-6 问题分析： 图7.6-1所示为图的广宽优先遍历。用队列来实现图的广度优先遍历：先从某个顶点出发，把这个顶点入队，作为队首元素。然后把跟队首元素相连的顶点再依次入队，最后队首元素出队。接着再把新的队首元素相连的所有顶点入队，新的队首元素出队。……如此下去，直到所有元素都出队，出队的顺序就是图的广度优先遍历序列。 1 2