第十周总结

这个题目就是最经典的并查集的题目，先对所有的点进行串联（先把所有的点进行串联），最后查找祖点为自身的点的总数，最终答案就是总数减一，思路很简单，代码也很简单，就是一道完完全全的并查集题目

 大体题意：给出每个花的价值和价格，给出组合，只要是组合相连的就必须全买，求在有限的钱内可以买到价值最大的为多少

这个题目就比较有意思了，开始做的时候还感觉跟上面的差不多啊，但是做着做着就发现不对劲了，就是我只会把他们相连其余（先相连，把所有所有的价值，花费放到一起），但是不能使他们价值最大化，后来我看了题解发现需要用到动态规划的思想也就是dp里面的经典的背包问题，在将解决完前面的问题后，从每个花进行判断，在可以买到的范围内不断地更新最大价值，最后将其输出。

总而言之：并查集的模板比较单一，大体思想就是把相连地点归到同一祖点，祖点为自身的点就当作一个独立的集合，然后可以根据自己想要实现的东西来进行 *** 作当然一般的并查集只显示最终的祖点，带权并查集就比较特殊可以显示多个祖点（目前还没遇到相关题目）。它的应用比较广泛，在部分题目中常与其他的算法联用，在做题时需要确定在哪个方面使用，怎么使用，是先查找相连，还是后查找相连，亦或是按照某种顺序进行相连，我认为这个就是并查集使用最重要的一点。

拓扑总结：

这个题的大意为：输入多组吃与被吃的关系，然后输出最长食物链个数%80112002 ，这个题目在上个搜索专题里面看到过，也是不出意料wa，直到现在我才知道这是一个拓扑类型的题目。

开始将吃与被吃的关系和每个点的入度出度进行读入，然后将那些入度为0的压入队列，

cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>a>>b;
        mp[a][b]=1;//吃与被吃的关系关系
        ch[a]++;//出度加一
        r[b]++;//入读加一
    }

从入度为0的开始往后拓展，只要有一个每有一个分支答案加一。

for(int i=1; i<=n; i++)
    {
        if(r[i]==0)
        {
            f[i]=1;
            q.push(i);//入度为零压入
        }
    }
    while(!q.empty()) 
    {
        int g=q.front();
        q.pop();//出队
        for(int i=1; i<=n; i++)
        {
            if(mp[g][i]==0)continue;//没有关系
            f[i]+=f[g];//路径加上路径

            r[i]--;//入度减一
            if(r[i]==0) //入度为零压入
            {
                if(ch[i]==0)//出度为0，走到头了
                {
                    ans+=f[i];//答案加上


                }
                q.push(i);
            }
        }
    }

本周拓扑做的题目不多，看了好几个都是跟基本的入度，关系，这几个点，所以没有记录，记录这个题目也是因为这个题目有一个出度。

拓扑其实就是有向的关系，可以用二维数组（速度快，内存太大）进行记录关系，也可以用可变数组（内存小，速度慢），也可以用链表来记录（比较麻烦，时间和内存处于前两者中间），剩下的就是考虑入度和出度，最后就是根据题目的各种要求来进行构建思路。

上课看的那个判断是否可以构成拓扑排序的那个题目我认为就是很难的一个题目，需要考虑的东西特别多，在没有完全压入的时候也需要进行判断是否有环。看完看懂代码细节花了我一个半小时，好吧确实我拓扑看的不多，题目就做了四个，能写的东西比较少，下个星期多做些后面的拓扑题目。