【题目来源】
/problem/U81206
【题目描述】
链式前向星模板题。
读入n个点，m条边，以及flag。若flag==1，则图有向，否则无向。
对每个点输出它的每一条边。
【输入格式】
第一行三个数：n，m，flag，题意如上所示。
第2~1+m行，每行三个数x，y，z。代表从x到y有一条长为z的边。
【输出格式】
若flag=1，则m行。若flag=0，则m*2行。
每行三个数，即该点的编号、所指向点的编号，边的长度。
先按第一个数升序排列，再以链式前向星中的顺序输出即可。 （其实就是i从1到n，再按顺序查找边输出即可）
特殊的，若该点无出边，单独一个空行。
【算法分析】
本题所需链式前向星核心知识点，详见：/hnjzsyjyj/article/details/126474608
【算法代码】
/* 链式前向星存图val[idx] 表示第 idx 条边的权值。e[idx] 表示第 idx 条边的终点。ne[idx] 表示与第 idx 条边同起点的最近一次被添加的边的编号。h[a] 表示以结点 a 为起点的最近一次被添加的边的编号。这个表述是在使用ne[idx]=h[a] 时，也即使用h[a]=idx++ 更新 h[a] 之前而言的。要特别注意这个语境。*/#include <bits/stdc++.h>using namespace std;const int maxn=2000005;const int maxm=4000005;int e[maxm<<1],ne[maxm<<1],h[maxn],val[maxm<<1],idx;// Undirected edges are special directed edges, open double// int e[maxm<<1],ne[maxm<<1],h[maxn],val[maxm<<1],idx;void add(int a,int b,int w) {val[idx]=w,e[idx]=b,ne[idx]=h[a],h[a]=idx++;}int main() {int n,m,f;cin>>n>>m>>f;memset(h,-1,sizeof(h));while(m--) {int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);if(f==0) add(b,a,c);}for(int i=1; i<=n; i++) {for(int j=h[i]; j!=-1; j=ne[j]) {printf("%d %d %d\n",i,e[j],val[j]);}}return 0;}/*in1:5 5 01 2 51 4 62 3 73 5 33 4 1out1:1 4 61 2 52 3 72 1 53 4 13 5 33 2 74 3 14 1 65 3 3--------in2:4 3 11 3 63 4 12 1 3out2:1 3 62 1 33 4 1*/
【参考文献】
/hnjzsyjyj/article/details/126475298
/hnjzsyjyj/article/details/126474608
/blog/szbszb/u81206-ti-xie
