环孢素软胶囊 https://m-mip.39.net/baidianfeng/mipso_4322187.html前向星是一种特殊的边集数组，把边集数组中的每一条边按照起点从小到大排序①，如果起点相同就按照终点从小到大排序②，并记录下以某个点为起点的所有边在数组中的起始位置③和存储长度④，那前向星就构造好了
head:记录以i为边集在数组中的第一个存储位置（起始位置）
len:记录所有以i为起点的边在数组中的存储长度
举例：
输入边的顺序：
12
23
34
13
41
15
45
经过①②排序后：
编号起点u终点v
经过③④处理后：
起始位置存储长度head[1]=1len[1]=3head[2]=4len[2]=1head[3]=5len[3]=1head[4]=6len[4]=2
注意：利用前向星会有排序操作，如果用快速排序时间至少为O（nlog(n)）,如果使用链式前向星可以避免
构建
/p>
structEdge{intto;intnext;intw;}edge[];
结构体元素一：edge.to表示第i条边的终点
结构体元素二：edge.next表示与i同起点的下条边存储位置
结构体元素三：edge.w为第i条边权值
数组head（一般初始化为-1），用来表示以i为起点的最近加入的一条边的存储位置（这里以i为起点的所有边的最后输入的那个编号）
构建边addEdge：
voidaddEdge(intu,intv,intw){edge[count].to=v;//存储终点,值域edge[count].w=w;edge[count].next=head;//存储下一条边head=count++;//存储最近一条边的存储位置}
回忆前面学过的数组构造邻接表：
voidaddEdge(intu,intv,intw){edge[count].next=head;//存储下一条边head=count;//存储最近一条边的存储位置edge[count].to=v;//存储终点,值域edge[count].w=w;count++;}
数据输入：
12
23
34
13
41
15
45
存储模拟：
addEdge函数记录边的终点下一条边存储位置记录边存储位置addEdge(1,2,0）edge[0].to=2edge[0].next=-1head[1]=0addEdge(2,3,0）edge[1].to=3edge[1].next=-1head[2]=1addEdge(3,4,0）edge[2].to=4edge[2].next=-1head[3]=2addEdge(1,3,0）edge[3].to=3edge[3].next=0head[1]=3addEdge(4,1,0）edge[4].to=1edge[4].next=-1head[4]=4addEdge(1,5,0）edge[5].to=5edge[5].next=3head[1]=5addEdge(4,5,0）edge[5].to=5edge[6].next=4head[4]=6
总结：head保存的是以i为起点的所有边中编号最大的那个，把这个当作i的第一条起始边的位置，遍历时虽然是倒着遍历（和输入顺序相反），但是不影响总体的结果正确性，以1为起点举例，编号分别为0,3,5，head[1]=5
遍历代码：
//遍历以i为起点的边for(inti=head;~i;i=edge.next){//解释：以1举例，head[1]拿到编号为5的边，然后edge[5].next存储着上一次//也就是下条边的编号head[1]等于3,然后edge[3].next拿到head[1]=0这个编号//最后如果0的后续没有了，拿到了-1，那么取反即为0，循环结束coutu""edge.to""edge.wendl;}
链式前向星模板：
#includeiostream#includecstringusingnamespacestd;constintMAXX=05;inthead[MAXX];//存以i为起点的最近加入的一条边的存储位置intindex;//边的编号structNode{//链式前向星structintto;//边的终点intw;//权值intnext;//相同起点的上一次加入的边的存储位置(指向下一条边在edge数组中的位置)}edge[MAXX*2];voidaddEdge(inta,intb,intw){//a起点,b终点,w权值edge[index].to=b;edge[index].w=w;edge[index].next=head[a];//head[a]:上一次加入的边的位置head[a]=index++;//更新以a为起点的最新加入的边的编号}intmain(){memset(head,-1,sizeof(head));//将head初始化为-1intn;cinn;for(inti=1;i=n;i++){//遍历以i为起点for(intj=head;~j;j=edge[j].next){couti""edge[j].to""edge[j].wendl;}}}
U：链式前向星
程序代码：结构体方法（分）
#includeiostream#includecstring#includecstdiousingnamespacestd;constintMAXX=1e6+1;inthead[MAXX];//存以i为起点的最近加入的一条边的存储位置intindex1;//边的编号structNode{//链式前向星structintnext;//相同起点的上一次加入的边的存储位置(指向下一条边在edge数组中的位置)intto;//边的终点intw;//权值}edge[MAXX*2];voidaddEdge(inta,intb,intw){//a起点,b终点,w权值edge[index1].next=head[a];//head[a]:上一次加入的边的位置head[a]=index1;//更新以a为起点的最新加入的边的编号edge[index1].to=b;edge[index1].w=w;index1++;}intmain(){memset(head,-1,sizeof(head));//将head初始化为-1intn,m,flag;cinnmflag;for(inti=0;im;i++){intx,y,z;scanf("%d%d%d",x,y,z);if(flag==1){addEdge(x,y,z);}else{addEdge(x,y,z);addEdge(y,x,z);}}for(inti=1;i=n;i++){//遍历以i为起点for(intj=head;~j;j=edge[j].next){printf("%d%d%d\n",i,edge[j].to,edge[j].w);//couti""edge[j].to""edge[j].wendl;}}return0;}?
数组方法：
#includebits/stdc++.husingnamespacestd;intn,m;intflag,i,ct,j,x,y,z;inthead[00001],NTX[],W[],VTX[];voidaddEdge(inta,intb,intw){NTX[ct]=head[a];head[a]=ct;VTX[ct]=b;W[ct]=w;ct++;}intmain(){memset(head,-1,sizeof(head));cinnmflag;for(i=0;im;i++){//cinxyz;scanf("%d%d%d",x,y,z);if(flag==0){addEdge(x,y,z);addEdge(y,x,z);}else{addEdge(x,y,z);}}for(i=1;i=n;i++){for(j=head;~j;j=NTX[j]){//couti""VTX[j]""W[j]endl;printf("%d%d%d\n",i,VTX[j],W[j]);}}return0;}
注意：一定要习惯于使用printf和scanf，效率真的比cin和cout高，否则会被TLE折磨死，淦！
一只小跃跃
