20131030: 森林结构的运用（poj： 树的转换，电话号码，物质分解记录）；带权并查集（食物链);C++输入；地图的基本使用
20131030: 森林结构的运用（poj： 树的转换，电话号码，物质分解记录）；带权并查集（食物链);C++输入；map的基本使用
第二道是关于树的建立与转换问题，大意是给出行走路径dud之类，要求出对应的树的深度， 以及转换为二叉树后树的深度， 首先需要根据行走路径建立树，这里采取的是数组存储方法， 每个节点用vector存储子节点表， 在此我们不需要另外用一个结构来存储转换后的二叉树，会比较麻烦，因为需要的仅仅是深度且后面用不上转换后的二叉树， 可以用传参的方式避免建树， 模拟建树过程，但是不进行存储，只是不断传参递归，求出深度即可！
第三道是关于森林的查找， 大意是给出一堆电话号码，判断是否存在一个电话号码是另外一个的前缀， 每输入一个电话， 将其加入森林中， 从当前森林的根开始，如果找到匹配则向下，否则另外添加一个分支并将后面的数字加入， 注意存在前缀的情况有两种， 一种是遇到叶节点， 一种是待加入的这个号码已经到末尾。 一旦发现前缀情况，后面直接让输入完成即可， 不必再做处理！
呵呵，昨天干掉的任务真不少， 关于森林与并查集，其实还有很多可以学的， 就必然森林的存储方式就有很多种， 但是我们一般选择自己习惯的就好， 因为一般条条大路通罗马嘛！~
本来是应该昨晚写这篇总结的，但无奈昨晚断网了，坑爹的校园网！！！~
昨天成功刷掉了树与森林的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 11:00
Description:
1. 主要考察点是数据的读入以及森林结构的建立（这里森林使用链式存储建立，子节点索引采用vector）
数据的读入（尤其是整行的读入）在C++中是个大问题，程序下方是我关于这个的小总结
2. 一个很那发现的小错误：避免使用重复定义！！！我在此的错误是：循环外定义了i，循环中的计数变量采用的又是int i形式，
循环外部又需要用到循环后的i值， 但是重复定义时采取的是层次划分策略，这个时候外部的i是未被更新的！！！
*/
#include<iostream>
#include<vector>
#include<cstring>
#include<stack>
using namespace std;
struct point
{
char s[300]; //可能需要增大
vector<point*> v;
point*father;
};
char s1[300],s2[300];
point *root=NULL;
bool find(point*p)
{
if(p!=root&&strcmp(p->s,s2)==0)
{
point *t=p->father;
int n=t->v.end()-t->v.begin(),i=0,j=0;
for(i=0;i<n;++i) //不要对i重复定义,会导致错误！
if(t->v[i]==p)
break;
for(j=i+1;j<n;++j)
cout<<t->v[j]->s;
return true;
}
int len=p->v.end()-p->v.begin();
for(int k=0;k<len;++k)
if(find(p->v[k]))
return true;
return false;
}
void Delete(point*p) //节省内存
{
int i,j,n=p->v.end()-p->v.begin();
for(i=0;i<n;++i)
Delete(p->v[i]);
delete p;
p=NULL;
}
int main()
{
int n,i,j;
cin>>n;
cin.get();
while(n--)
{
stack<point*> a;
point *p1=NULL, *p2=NULL;
root=new point; //森林的虚拟根
root->father=NULL;
a.push(root);
while(1)
{
cin.getline(s1,300);
//cin.get();
int len=strlen(s1);
if(len==0) break;
if(s1[0]=='{')
a.push(p2);
else if(s1[0]=='}')
a.pop();
else //为物质名称（数据）
{
p1=new point;
strcpy(p1->s,s1);
point*t=a.top();
p1->father=t;
t->v.push_back(p1);
p2=p1; //p2用于暂时存储上一个
}
}
cin.getline(s2,300);
//遍历找匹配
if(!find(root))
cout<<"No";
cout<<endl;
Delete(root);
cin.get();cin.get();
}
cin.getline(s1,300);
return 0;
}
//关于C++几种数据读入方式的问题（已经过实验验证！）
/*
char c;
int a,b;
string s;
char str[20]; //cin输入数据前会跳过空格回车TAB
//cin>>c;cout<<c; //cin（输入数据后）遇到空格回车TAB都结束（即使要读入的是字符！!!)
// cin>>a>>c;
//cout<<a<<c;
cin>>a;//cin.get(); //cin（输入数据后）光标不会移到回车和空格和TAB后面 ，注意TAB是一个字符，只是长度相当于多个空格（数量可指定）
cin.getline(str,20);
cout<<a<<endl<<str<<endl;
cin.getline(str,20); //不读入回车，但光标会移到回车后面
cout<<str<<endl;
cin>>a;cin.get(); //getline与cin.getline()光标移动情况相同
getline(cin,s);
cout<<a<<endl<<s<<endl;
getline(cin,s);
cout<<s<<endl;
*/
第二道是关于树的建立与转换问题，大意是给出行走路径dud之类，要求出对应的树的深度， 以及转换为二叉树后树的深度， 首先需要根据行走路径建立树，这里采取的是数组存储方法， 每个节点用vector存储子节点表， 在此我们不需要另外用一个结构来存储转换后的二叉树，会比较麻烦，因为需要的仅仅是深度且后面用不上转换后的二叉树， 可以用传参的方式避免建树， 模拟建树过程，但是不进行存储，只是不断传参递归，求出深度即可！
/*
Name: 树的转换
Copyright: poj
Author: xiaoli
Date: 30/10/13 11:02
Description:
1. 通过行走路径（dud之类）建立一棵树，这里给出的是用数组存储建树的方法
2. 注意多组数据必须有清空操作（初始化）， 含有STL结构时不能直接用memset!!
3. 将森林转换为二叉树并求得深度（递归），这里未建立二叉树而是直接求深度
（通过递归函数的传参可以避免结构的建立，直接求得所需的量，但这是在不需要再次用此结构的基础上！）
*/
#include<iostream>
#include<vector>
#include<string>
using namespace std;
//数组实现（需要用一个变量记录当前用到的数组位置，数组下标就是索引）
struct point
{
vector<int> v;
int father;
int depth;
}dot[10005]; //0表示根节点
int dotpos; //用于不断加入元素的记录
string s;
int h1,h2;
void create_tree(int father, int pos) //pos表示在s中的位置
{
if(pos>=s.length())
return;
if(s[pos]=='d') //新建一个节点
{
dot[dotpos].depth=dot[father].depth+1;
if(dot[dotpos].depth>h1)
h1=dot[dotpos].depth;
dot[dotpos].father=father;
dot[father].v.push_back(dotpos);
dotpos++; //在下一个递归前必须更新
create_tree(dotpos-1, pos+1);
}
else if(s[pos]=='u') //回到父节点
{
create_tree(dot[father].father, pos+1);
}
}
void transfer(int father, int vpos, int depth) //将树转换为二叉树（只求深度，不建树）
{
int n=dot[father].v.end()-dot[father].v.begin(),i,j;
if(depth>h2)
h2=depth;
if(n<=vpos) //已终止
return;
int t=dot[father].v[vpos];
transfer(t, 0, depth+1);
transfer(father, vpos+1, depth+1);
}
void Delete(int root)
{
int n=dot[root].v.end()-dot[root].v.begin(),i,j;
for(i=0;i<n;++i)
Delete(dot[root].v[i]);
dot[root].depth=0;
dot[root].father=0;
dot[root].v.clear();
}
int main()
{
int num=0,i,j;
while(cin>>s)
{
if(s=="#") break;
num++;
dotpos=1;h1=0;h2=0;
create_tree(0,0);
transfer(0,0,0);
cout<<"Tree "<<num<<": "<<h1<<" => "<<h2<<endl;
Delete(0); //这里数组必须初始化！(不能直接用memset)
}
return 0;
}
第三道是关于森林的查找， 大意是给出一堆电话号码，判断是否存在一个电话号码是另外一个的前缀， 每输入一个电话， 将其加入森林中， 从当前森林的根开始，如果找到匹配则向下，否则另外添加一个分支并将后面的数字加入， 注意存在前缀的情况有两种， 一种是遇到叶节点， 一种是待加入的这个号码已经到末尾。 一旦发现前缀情况，后面直接让输入完成即可， 不必再做处理！
这道题中需要用map优化搜索（宽度范围），分找到和找不到两种情况，需要对map的使用比较熟悉，map的使用基本方法附在这个程序后部！
/*
Name: 电话号码
Copyright: poj
Author: xiaoli
Date: 30/10/13 11:08
Description:
1. 将输入的电话号码加入森林，加入时考虑是否有前缀重合现象（同样用数组存储，不会出现错用指针的现象）
2. 注意确定合适的数组大小（否则会RE)，注意到每个电话号码不超过10位，所以搜索时不用担心深度的问题，
但广度上随着深度递增增加可能特别快，需要用map匹配关系方便查找（map的使用附在程序下方！）
3. 多组数据需要清空，注意递归函数中最好不要使用全局变量（尤其是在循环中！）
*/
#include<iostream>
#include<map>
#include<string>
using namespace std;
//虚拟根节点是0， v为空时表示叶节点
map<char,int> dot[60000]; //方便每加入一个号码时的查找
//根据号码数量上限和数字种类推出数组范围
void Delete(int root) //用于每组测试数据结束后的清空
{
map<char,int>::iterator p; //不能用全局变量的迭代器（递归中前一轮会影响循环的后一个！)
for(p=dot[root].begin();p!=dot[root].end();++p)
Delete(p->second);
dot[root].clear();
}
int main()
{
int t,n,i,j;
cin>>t;
string s;
map<char,int>::iterator it;
while(t--)
{
cin>>n;
bool flag=false; //未出现前缀重合
int dotpos=1;
while(n--)
{
cin>>s;
if(flag) //已经无需再处理
continue;
int len=s.length(),p=0; //p表示当前树的根
for(i=0;i<=len;++i)
{
if((p!=0&&dot[p].empty())||i==len) //重合有两种情况
{
flag=true;
break;
}
it=dot[p].find(s[i]);
if(it==dot[p].end()) //没找到,则将此后的节点加入这棵树中
{
for(j=i;j<len;++j,++dotpos)
{
dot[p].insert(make_pair(s[j],dotpos));
p=dotpos;
}
break;
}
else
{
p=it->second;
}
}
//不能直接break，输入还没完成
}
if(flag)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
Delete(0);
}
return 0;
}
/*
STL map常用操作简介
1。目录
map简介
map的功能
使用map
在map中插入元素
查找并获取map中的元素
从map中删除元素
2。map简介
map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。对于迭代器来说，可以修改实值，而不能修改key。
3。map的功能
自动建立Key － value的对应。key 和 value可以是任意你需要的类型。
根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。
快速插入Key - Value 记录。
快速删除记录
根据Key 修改value记录。
遍历所有记录。
4。使用map
使用map得包含map类所在的头文件
#include <map> //注意，STL头文件没有扩展名.h
map对象是模板类，需要关键字和存储对象两个模板参数：
std:map<int, string> personnel;
这样就定义了一个用int作为索引,并拥有相关联的指向string的指针.
为了使用方便，可以对模板类进行一下类型定义，
typedef map<int, CString> UDT_MAP_INT_CSTRING;
UDT_MAP_INT_CSTRING enumMap;
5。在map中插入元素
改变map中的条目非常简单，因为map类已经对[]操作符进行了重载
enumMap[1] = "One";
enumMap[2] = "Two";
.....
这样非常直观，但存在一个性能的问题。插入2时,先在enumMap中查找主键为2的项，没发现，然后将一个新的对象插入enumMap，键是2，值是一个空字符串，插入完成后，将字符串赋为"Two"; 该方法会将每个值都赋为缺省值，然后再赋为显示的值，如果元素是类对象，则开销比较大。我们可以用以下方法来避免开销：
enumMap.insert(map<int, CString> :: value_type(2, "Two"))
6。查找并获取map中的元素
下标操作符给出了获得一个值的最简单方法：
CString tmp = enumMap[2];
但是,只有当map中有这个键的实例时才对，否则会自动插入一个实例，值为初始化值。
我们可以使用Find()和Count()方法来发现一个键是否存在。
查找map中是否包含某个关键字条目用find()方法，传入的参数是要查找的key，在这里需要提到的是begin()和end()两个成员，分别代表map对象中第一个条目和最后一个条目，这两个数据的类型是iterator.
int nFindKey = 2; //要查找的Key
//定义一个条目变量(实际是指针)
UDT_MAP_INT_CSTRING::iterator it= enumMap.find(nFindKey);
if(it == enumMap.end()) {
//没找到
}
else {
//找到
}
通过map对象的方法获取的iterator数据类型是一个std::pair对象，包括两个数据 iterator->first 和 iterator->second 分别代表关键字和存储的数据
7。从map中删除元素
移除某个map中某个条目用erase()
该成员方法的定义如下
iterator erase(iterator it); //通过一个条目对象删除
iterator erase(iterator first, iterator last); //删除一个范围
size_type erase(const Key& key); //通过关键字删除
clear()就相当于 enumMap.erase(enumMap.begin(), enumMap.end());
*/
要保证满足这个关系是很麻烦的，因为情况实在太多了，难以全部考虑， WA是意料之中， 后面不得不放弃这个想法！！！（这个想法作为失败的典例还是保留在程序的注释中了）， 这道题是借助他人的教程才弄清楚的，当然最终代码是自己写的，但算法是学来的， 带权并查集使用起来并不简单！
关于这道题， ****网站中有别人分享的很详细的解释， 重要的是理解其原理和公式的推导，因为带权并查集的变化特别多， 可以参见我的收藏，或者直接搜那个博客
：http://blog.****.net/c0de4fun/article/details/7318642
我的感悟全部集成在程序中：
/*
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的relation
dot[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操作，因为根都是相同的，同时高度最多为2
if(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);
else
dot[t1].eat2=t2;
if(dot[t2].eat1)
Union(t1, dot[t2].eat1);
else
dot[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);
else
dot[k1].eat1=dot[k2].eat2;
}
else if(dot[k1].eat1)
{
if(dot[k2].eat2)
Union(dot[k1].eat1, dot[k2].eat2);
else
dot[k2].eat2=dot[k1].eat1;
}
}
}
cout<<wrongnum<<endl;
return 0;
}
*/
呵呵，昨天干掉的任务真不少， 关于森林与并查集，其实还有很多可以学的， 就必然森林的存储方式就有很多种， 但是我们一般选择自己习惯的就好， 因为一般条条大路通罗马嘛！~
总算把昨天的日记补完了！~~~