首先注：下面出现的代码完全没经编译，不保证编译成功，大家当伪代码看较好~
在OIer的世界里，有一种奇妙的东西，叫图论。。 而对于计算机，我们并不能将一张图输入，而需要一些存图方式 比如下面这张图（画得不好看勿喷~）： 最简单的存图方式是邻接矩阵 *在一个n*n的矩阵中，第(i,j)个格子的值表示从i到j这条边的边权。。 上图用邻接矩阵表示就是：
-012345600305000130200002020200035020350400030205000520860000080图的储存结构：
int tu[N][N];建边：
inline void build(int x,int y,int z){ //建从x到y边权为z的边 tu[x][y]=z; //单向边 #ifdef DOUBLE_EDGE tu[y][x]=z; //双向边 #endif }枚举边：
int x=start; for(int i=0;i<n;i++) if(tu[x][i]){ //若不为0表示相连 int y=i; //跑到i的点 }这个东西有个显而易见的缺点，O(n^2)的效率就决定了无法处理任何大规模的数据。。 而O(nlogn)的算法中的n基本都在10^5级别。。数组都开不开啊_ (:з」∠) _
所以我们需要邻接表，这样时间、空间效率都被控制在O(m)级别（m为边数） 正统的邻接表是用指针…… 邻接表对于每个点主要保存了以下东西： - 这个点出发的第一条边 - 每条边（和下面的都指该点出发的边）所指向的点 - 每条边的边权（data域） - 每条边指向的下一条边 储存的结构基本上是这样的：
struct edge{ int to,data; etype *next,*pair; //pair为反向边，视情况而建 edge(){} edge(int t,int d,edge* nxt):to(t),data(d),next(nxt){} //dalao们发现C++的new实在是太慢了，所以要自己写一个orz void* operator new(unsigned,void* p){return p;} }*e[N]; /*还有一个*/int Pe=0; //记录了边的总数建边：
void build(int x,int y,int z){ e[x]=new(Pe++)edge(y,z,e[x]); //指向y，边权z，上一条边是上一个e[x].. #ifdef DOUBLE_EDGE e[y]=new(Pe++)edge(x,z,e[y]); e[x]->pair=e[y]; e[y]->pair=e[x]; #endif }枚举边：
int x=start; for(etype *i=e[no];i;i=i->next) int y=i->to;嗯，很好，我们现在有了存图的利器 但是，指针的特性决定了对我们精确的要求。。 不禁想起了指针调试的恐惧 所以，我们应该是有更简(ju)便(ruo)的方法的： 比如，数组模拟……（这应该也是应用最广泛的吧……） 于是存储结构变成了：
struct edge{ int to,next,data; }e[M]; int v[N],tot=0; //v数组就是很多很多dalao的first数组，存点i出发的第一条边备查 //网络流图中tot为了异或找反向边容易可以置为1..建边：
void build(int x,int y,int z){ e[++tot].to=y; e[tot].next=v[x]; e[tot].data=z; v[x]=tot; #ifdef DOUBLE_EDGE e[++tot].to=x; e[tot].next=v[y]; e[tot].data=z; v[y]=tot; #endif }枚举边：
int x=start; for(int i=v[x];i;i=e[i].edge) int y=e[i].to;对就是这样。。 其实似乎写到这里就可以结束了。。 但是其实还是有一种写法的。。 比如，C++的盆友们，还记得你们的STL么？ vector也可以用来存邻接表哦（下面我给出没有边权的）~ （而且似乎省选开O2什么的STL会格外跑得快） 存储结构？
vector<int> e[N];建边：
void build(int x,int y){ e[x].push_back(y); //媲美邻接矩阵的简便.. #ifdef DOUBLE_EDGE e[y].push_back(x); #endif }枚举边：
int x=start; for(/*unsigned*/int i=0;i<e[x].size();i++){ //不想要warning的可以加unsigned.. int y=e[x][i]; }行了，就介绍这么多。。。 希望对大家有帮助，希望大家用的开心~~
