首页 > 代码库 > 靠二进制画几何[图论]
靠二进制画几何[图论]
今天来浅谈一下图，听说自己写总结的人grade++，rp++。
像我这样可爱的人怎么能错过这个机会呢嘤嘤嘤。
毕竟图至少啃了15day++。
恩曾经的小弱渣从来都是仰望高端玩家虐图论
听说noip上一年考两道大图(つд⊂)而小弱渣还没学到
吓得本宝宝虎躯一震！！
恩废话不多说，来开正文。
-------------------我是萌哒哒的分割线--------------------
刚开始先学图的储存。
- 邻接矩阵
邻接矩阵就是跟二维数组长得一毛（mu）一样奇奇怪怪的东xi
1 #include<iostream> 2 using namespace std; 3 int n,a[100][100]; 4 int main() 5 { 6 cin>>n; 7 //直接给出邻接矩阵，直接读。 8 for(int i=1;i<=n;i++) 9 for(int j=1;j<=n;j++)10 cin>>a[i][j];11 //给出两个顶点和权值12 for(int i=1;i<=n;i++)13 {14 int xx,yy,vv;15 cin>>xx>>yy>>vv;16 a[xx][yy]=vv;17 //双向图时18 a[yy][xx]=vv;19 }20 //给出每个顶点的临界点21 for(int i=1;i<=n;i++)22 {23 int k;24 cin>>k;25 for(int j=1;j<=k;j++)26 {27 int x;28 cin>>x;29 a[i][x]=1;30 a[x][i]=1;31 }32 }33 return 0;34 }
2.邻接表
第一次看这玩意的时候内心万般草泥马奔过。
这TM都是什么玩意
后来经过滑稽大师cdc柴大叔的指导下，莫名其妙知道了些什么
然而教材太过简单，时常还会有些错的
小弱渣花了一整节自习课照着书上画了一幅图，发现！原来！跟书上一毛（mu）一样。本宝宝不开心，哦是十分不开心。
这大概是这个样子的
1 #include<iostream> 2 using namespace std; 3 int n; 4 int link[10010],len=0; 5 struct ha 6 { 7 int y,v,next; 8 }e[10010]; 9 void insert(int xx,int yy,int vv)10 {11 e[++len].next=link[xx];12 link[xx]=len;13 e[len].y=yy;14 e[len].v=vv;15 }16 int main()17 {18 cin>>n;19 int xx,yy,vv;20 for(int i=1;i<=n;i++)21 {22 cin>>xx>>yy>>vv;23 insert(xx,yy,vv);24 insert(yy,xx,vv);25 }26 return 0;27 }
如果出现重边！邻接矩阵必须判断！！
-----------------我是萌萌哒的分割线------------------
DFS：以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；当没有未访问过的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有的顶点都被访问过。
靠二进制画几何[图论]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。