20131030: 森林结构的运用（poj： 树的转换，电话号码，物质分解记录）；带权并查集（食物链);C++输入；map的基本使用

本来是应该昨晚写这篇总结的，但无奈昨晚断网了，坑爹的校园网！！！~

昨天成功刷掉了树与森林的4道题，加上前天做掉的并查集入门题， 树与森林宣告终结！不过这一章的确学到很多东西，尤其是编程技巧和一些细节处理！

首先讲三道比较简单的吧， 主要就是考察森林的建立与一些基本操作， 包括与树，二叉树的相互转换，查找，更新等等。

森林的建立我目前比较熟悉且常用的是两种方式：

一种是数组存储， 需要用一个变量来记录当前数组的存储位置，每加入一个元素都得更新此变量，利用数组的下标作索引，十分方便，也不用担心指针的使用这种问题，因为根本用不上指针，我除了最开始的物质分解记录 后面都用的数组存储， 可能最开始使用会不习惯！~；（另外就是一定要仔细确定题目要求后来推出应该规定的数组最大容量，

否则会RE！因为这种存储方式无法动态分配！）

一种是链式存储，最白痴的存储方式，也是最万能的存储方式，实在找不到好的存储结构就用链式， 只不过动态操作内存有点麻烦，还有就是指针的使用容易出错， 改变指针指向时一定要注意是否有冲突！还有就是程序结束时或者每一组测试数据结束时要手动清空内存， 否则在数据量大时可能造成错误（虽然在计算机中整个程序结束时会自动执行清空操作，但那个不是你自己的程序的操作！！！）

两种方法只是在形式上差别比较大， 关于子节点索引表其实都是用相同的方式解决，因为子节点数目不定，可以用vector(顺序固定）， set(排好序）， map（方便根据一个key值来进行查找， 将搜索复杂度降到O（lgn），无论key是何种类型都适合！）。 注意set和map都会改变顺序， 而vector在需要大量查找操作时效率低下，基本上都会超时！

值得一提的是， 在为完全k叉树时，又可以采取另一种数组存储方式，前面的数组存储方式相当是将指针换成整数下标索引，而且基本上是深度优先存储， 而这个可以按照层遍历的顺序进行存储， 也不用记录节点索引下标， 因为存储时下标间的关系就被定好了，这种情况下用这种存储操作会十分方便，空间上索引值， 时间上比如想找到某个深度的元素， 不用遍历直接计算下标即可，所以说空间和时间上都被优化了！~对于标号为i的节点（根为1）， 它的子节点是从k*i-(k-2)到k*i+1，

最后一层最后面一部分可能有些不存在！~ 它的父节点是(i-2)/k+1, 注意正负都是向0取整！

这种存储方式只适合完全k叉树，否则是对存储空间的严重浪费！

懂得基本操作后就可以直接练习了，每道题中都有一些独特的地方， 物质分解记录 这道题中主要是一个数据读入方式的问题， 这就需要我们对各种输入方式了解清楚，特别是输入后光标的移动情况！！！ 关于输入问题的说明附在这道题的程序下方， 经过我自己逐个实验的，可以信赖！

/*  Name: 食物链   Copyright: poj  Author: xiaoli   Date: 30/10/13 13:23  Description:   1.带权并查集：利用食物链中三个类型的循环捕食关系确定权值，也就是relation（与父节点的关系)  2. 同一集合中的说明关系已经确定，否则关系未定，同一集合不代表等价类，具体关系可以通过运算得到，  其中很关键的是利用食物链的三角循环这个性质， 注意不满足传递性，即A吃B，B吃C，不能得到A吃C，  反而得到的是C吃A， 也就是说， 利用A对B的关系以及B对C的关系可以运算得到A对C的关系  3. 每次节点挂载（路径压缩，合并操作）都得做关系值的更新  4. 数据结构搭建好后，重点在于关系值公式的推导！！！（运算结果模3， 同余定理）  （1）假如B对父节点A的关系是t， 则A对B的关系是（3-t)%3;  （2）假如B对A的关系是t1， C对B的关系是t2, 则C对A的关系是(t1+t2)%3；  Union操作中的关系更新公式也就是根据上面两个法则推出的，期间要用到同余定理！  注意若type（a,b)表示指令（1 或2），则type-1就表示b对a的关系！ */#include<iostream>#define MAX 50005#define SAME 0         //与父节点类型相同#define EATEN 1        //被父节点吃#define EAT  2         //吃父节点using namespace std;struct point{int father;int relation;             //食物链类型：与父节点的关系}dot[MAX];void Init(int n)        //初始化并查数组{int i;for(i=1;i<=n;++i){dot[i].father=i;               //初始化为独根树dot[i].relation=SAME;   //自己跟自己等价，满足自洽性（很重要！！！）}}//对于下面这个函数，弄清楚高度问题以及挂载关系问题！int Find(int x)        //找到对应的父节点， 执行路径压缩后能够保证每棵树高度不超过2（根为0） {       //同时更新这个节点的relation（一些操作后子节点未改变，但后面总可计算出来）if(dot[x].father==x)return x;int tmp=dot[x].father;               //!!!!!dot[x].father=Find(dot[x].father);   //先更新其父节点的关系dot[x].relation=(dot[x].relation+dot[tmp].relation)%3; //再更新自己的关系return dot[x].father;}void Union(int x,int y, int a, int b, int type) //a,b分别是x,y的根节点，type指定合并类型（关系）{dot[b].father=a;                            //这里确定了顺序，下面就要根据这个顺序确定关系值！ //关键是计算合并后b对a的relationdot[b].relation=(3-dot[y].relation+type-1+dot[x].relation)%3;}int main(){int n,k,i,j;cin>>n>>k;int wrongnum=0, type=0,a=0,b=0;Init(n);while(k--){cin>>type>>a>>b;if(a>n||b>n||(type==2&&a==b)){wrongnum++;continue;}//先找到对应的根， 再观察是否在同一个集合中//在同一集合中说明关系已经确定(可以做判断），否则关系未确定int t1=Find(a),t2=Find(b);if(t1!=t2)            //在不同集合中,直接合并即可{Union(a,b,t1,t2,type);continue;}//下面是在同一集合中的情况，不用合并，但需要分析正误!//注意下面要直接对a,b操作，因为根都是相同的，同时高度最多为2if(type==1){                                          //相等关系可以不运算直接判断if((3-dot[b].relation+dot[a].relation)%3!=0)wrongnum++;}else if(type==2){if((3-dot[b].relation+dot[a].relation)%3!=2)wrongnum++;}}cout<<wrongnum<<endl;return 0;}/*#include<iostream>       //这种数据结构十分麻烦， 处理起来情况太多!!!!!using namespace std;//吃的关系以祖先为准struct point{int father;          //本类的链接int eat1;            //吃自己的int eat2;            //自己吃的}dot[50005];             //编号从1，注意三角循环关系int Find(int x){if(dot[x].father==x)return x;dot[x].father=Find(dot[x].father);return dot[x].father;}void Union(int x, int y){                                     //这里传入的是每个等价类的根dot[x].father=y;dot[y].eat1=Find(dot[y].eat1);dot[y].eat2=Find(dot[y].eat2);}int main(){int n,k,i,j;cin>>n>>k;int wrongnum=0,type=0,a=0,b=0;for(i=1;i<=n;++i){dot[i].father=i;dot[i].eat1=dot[i].eat2=0;      //初始化时不存在食物关系}while(k--){cin>>type>>a>>b;if(type==1){int t1=Find(a), t2=Find(b);if(t1==t2) continue;if(dot[t1].eat2==t2||dot[t2].eat2==t1)   //互为捕食关系{wrongnum++;continue;}Union(t1,t2);                   }else if(type==2){if(a==b||a>n||b>n){wrongnum++;continue;}int t1=Find(a),t2=Find(b);if(t1==t2||dot[t2].eat2==t1){wrongnum++;continue;}if(dot[t1].eat2)                    //等价类已经存在Union(t2, dot[t1].eat2);elsedot[t1].eat2=t2;if(dot[t2].eat1)Union(t1, dot[t2].eat1);elsedot[t2].eat1=t1;int k1=Find(t1),k2=Find(t2);if(dot[k2].eat2){if(dot[k1].eat1)Union(dot[k2].eat2, dot[k1].eat1);elsedot[k1].eat1=dot[k2].eat2;}else if(dot[k1].eat1){if(dot[k2].eat2)Union(dot[k1].eat1, dot[k2].eat2);elsedot[k2].eat2=dot[k1].eat1;}}}cout<<wrongnum<<endl;return 0;}*/

呵呵，昨天干掉的任务真不少， 关于森林与并查集，其实还有很多可以学的， 就必然森林的存储方式就有很多种， 但是我们一般选择自己习惯的就好， 因为一般条条大路通罗马嘛！~

总算把昨天的日记补完了！~~~