第七周总结

这周接近尾声了，与其他周不同的是这周没打比赛，总感觉缺了点啥。这周经历的最大的事就是发烧吧，从星期五中午开始，这两天就没咋学，可想而知在空余时间最多的周末没学习学的内容肯定不是特别多，但是毕竟学了这么久的搜索，尽管这个星期用的时间比上个星期短很多，但是看的内容却和上个星期差不多，真的是感觉越看越快，有些东西也了解的更深了一些。现在解释深搜和广搜的两个过程图已完全刻在脑子里了。这周看博客还出现了一些新的概念。这个星期去参加ACM协会的面试了，问了俩问题第一个问题是vector原理，我第一个想到的是程序设计B类中的new我感觉他俩原理差不多都是申请空间，第二个问题是广搜实现用的queue可否换为栈，当时听完我的第一反应是不可以，当时对栈的理解只是后进先出，对队列的理解在先进先出上，随着面试的进行我发现有人却说可以，我找了很多资料但是都并没有了解到相关内容，我意识到自己掌握的知识实在是太少了，虽然说知识是没用的，但是要获得有用的东西，必须要走有知识这一步。

总结一下我这星期看的题思路。

1、最大食物链计数 - 洛谷

看题解时了解到新的概念拓扑排序，用的是bfs。

题意：给出两个正整数 n,m，表示生物种类 n 和吃与被吃的关系数 m

接下来 m行，每行两个正整数，表示被吃的生物A和吃A的生物B

求食物链条数。

思路：要创建两个数组，分别用于储存不同生物在A和B位置出现的次数，bfs首先要做的工作是，应该如何开始，起点是啥，m行数据中B的根据食物链定义，可知一定不含生产者，即出现次数为0的生物，故寻找出来可作为bfs起点，（但是我想的是为啥不从最高营养级取，只要m行数据中A的出现次数为零的不就行了，现在想确实可以，for里面套while，找到生物量为0的，但是面临一个问题是，现在学的内容都是从一个点出来分出多个点，该如何从多个点到一个点确实还不知道咋实现，我想应该涉及方向的问题，有可能也根本无法实现，就算是实现也是代码又长又难懂），要考虑如何知道当下营养级所形成的链条数呢？当下营养级形成的链数是所有上一个营养级所形成链的总和，其实就和递归思想差不多，那如何设置条件使得ans链条能够变化呢？当确定一个生物后，让m行数据中B中出现该生物的次数为0，且要保证A中不含有该生物，即可这个营养级所形成的链条数加入到ans中去。还有下面这个代码中continue//有没有都行，我感觉加上好可以减少时间复杂度。

#include
using namespace std;
int n,m,ru[5005],chu[5005],a,b,f[5005],ans;
int mp[5005][5005];
queue q;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		scanf("%d%d", &a, &b);
		mp[a][b]=1;//记录关系
		chu[a]++;
		ru[b]++;//记录入度和出度
	}
	for(int i=1;i<=n;i++){
		if(ru[i]==0) {
			f[i]=1;
			q.push(i);//入度为零的入队
		}
	}
	while(!q.empty()){//队列不为空
		int a=q.front();
		q.pop();//出队
		for(int k=1;k<=n;k++){
			if(mp[a][k]==0)continue;
			f[k]+=f[a];//更新
			f[k]%=80112002;
			ru[k]--;//食物少了一个
			if(ru[k]==0){//入队为零才入队
				if(chu[k]==0){
					ans+=f[k];
					ans%=80112002;
                    continue;//有没有都行
				}
				q.push(k);
			}
		}
	}
	cout<

for(int i=1;i<=n;i++){
            if(!vis[i] and z[i]-r<=0) search(i);
            if(pd==1){ cout<<"Yes"<

double dis(int a,int b){
    double x1=(double)x[a],y1=(double)y[a],z1=(double)z[a];
    double x2=(double)x[b],y2=(double)y[b],z2=(double)z[b];
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
}