首页 > 代码库 > 吉林省2017年冬令营DAY5
吉林省2017年冬令营DAY5
DAY5 图论
最短路径,最小生成树,拓扑排序,连通分量,二分图。
总的来说,day5这一天讲的东西听得不怎么明白,准备冬令营过后回去慢慢理解。
首先讲的是邻接矩阵
假如有n个点,则建立一个n*n的二维数组,在i行的j位上做一个标记表示i与j连通。
第二点讲的是链式前向星
当天听的时候,听得很不明白,后来听大佬讲了一下,上网搜索了一些资料,还算是懂了些。
先建立一个_edge结构体,内含{to,next,val},一个Head[]数组,一个计数器tot
代码1 #define MX 10000 2 struct _edge 3 { 4 int to,next,val; 5 }edge[MX]; 6 int head[MX],tot;因为最后是从后向前遍历,所以,在构建的时候把edge[tot].to指向v,把权值w赋于edge[].val,把edge[].next指向head[u](起点之前最后一个边),head[u]指向tot。
代码(add)1 void add(int u,int v,int w) 2 { 3 edge[tot].to=v; 4 edge[tot].val=w; 5 edge[tot].next=head[u]; 6 head[u]=tot++; 7 }
吉林省2017年冬令营DAY5
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。