图论习题整理
需要知道树的遍历方法,分别前中后序,代表着先访问根节点,左子树,右子树,或是左中右,或是左右中
现在给同一棵树的中后两个序列,求前序,
首先清楚这样的性质:
1.对于某个树(无论是子树还是本体,只要是棵完整的树就行),其前序遍历序列的第一个节点肯定是它的根,就是对于节点,其位于的层数越浅越靠后
对于后序遍历也类似,只是相反
2.中序遍历虽然看起来很乱,啥用没有,但是它在划分子树(是左子树还是右子树)上有着不可或缺的作用,毕竟对于一个数的中序序列,一旦找到根节点,其左子树和右子树就非常好确定了
3.因为无论哪种遍历,都是挨个按照子树的顺序去遍历的,所以子树的序列在总序列里面一定是连续的,不存在穿插的情况
那么这就好办了,递归处理规定区间的序列就好
先将后序序列中最后一位取出,在中序序列中进行查找,然后规定中序序列的左右子树,也就是下一步的目标,进行递归处理
同时,我们注意到中序遍历和后序遍历的子树区间并不对应,所以要同时处理两个序列需要处理的区间,中序好说,关键是后序
我们发现对于后序序列,其构成一定为:(左子树)+(右子树)+(根节点)
就是一定是这样有序的
那么只要处理出区间长度(就是子树大小,当然左右需要分开的),差不多这题就结了,
记得我们在处理中序序列时找的根节点吗?就用它的下标来作区间处理
这里的区间表示有点考验思维,建议自己推(不推反正下面也有代码
#include#include #include #include #include using namespace std;char tar1[10];char tar2[10];int len;inline int find(const char &x){ for(int i=1;i<=len;i++) if(tar1[i]==x) return i;}inline void search(int l1,int r1,int l2,int r2){ printf("%c",tar2[r2]); int t=find(tar2[r2]); if(t>l1) search(l1,t-1,l2,r2+t-r1-1); if(t
没有与最短路及其算法相关的图论整理博客不是好博客(本来就不是
题目翻译:
给了一堆数据范围(题目中的小路不会耗10000秒什么的也是数据范围啦...)
然后问你有没有负环
(我兴致冲冲想写最短路你给我看这个?
看到题,看到环,不要什么时候都想着tarjan...tarjan只是存强连通分量的算法,虽然环也可以,但是用于找负环...有SPFA为什么不用呢?
SPFA基于广搜BFS,深搜DFS当然可以过但是对于那道负环模板题就会被卡掉
为什么SPFA(或者Bellman-Ford)会被负环卡掉?
因为SPFA见到可以更新到很小,就一定会进行更新和入队(准备下一步松弛)
那么负环正是可以"无限缩小"的这么一种东西,就这样,SPFA在无限的更优方案中死掉了
每一个点只要入队超过n-1次,就说明有负环,因为每个店最多被其他每个点各松弛一次,多了就是在里面绕起来了,用它判负环就是了
代码:
#include#include #include #include using namespace std;int t;int n,m;struct Ed{ int to,nxt,dis;}ed[50005];int head[20005];bool vis[20005];int tms[20005];int ednum;inline void add(const int &from,const int &to,const int &dis){ ed[++ednum].to=to; ed[ednum].dis=dis; ed[ednum].nxt=head[from]; head[from]=ednum;}int dis[20005];queue q;inline bool spfa(){ memset(dis,0x3f,sizeof dis); memset(vis,0,sizeof vis); memset(tms,0,sizeof tms); dis[1]=0; vis[1]=1; tms[1]++; q.push(1); while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i;i=ed[i].nxt){ if(dis[ed[i].to]>dis[u]+ed[i].dis){ dis[ed[i].to]=dis[u]+ed[i].dis; if(!vis[ed[i].to]){ q.push(ed[i].to); vis[ed[i].to]=1; tms[ed[i].to]++; if(tms[ed[i].to]>=n) return 1; } } } } return 0;}int main(){ scanf("%d",&t); while(t--){ memset(ed,0,sizeof ed); memset(head,0,sizeof head); ednum=0; int w; scanf("%d%d%d",&n,&m,&w); for(int i=1;i<=m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } for(int i=1;i<=w;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,-c); } bool ok=spfa(); if(ok) printf("YES\n"); else printf("NO\n"); }return 0;}