PDF文档公众号回复关键字:20240930
1 2020 CSP-J 题目1 优秀的拆分
[题目描述]
链式前向星模板题，读入n个点，m条边，以及flag，若flag==1则图有向，否则无向。对每个点输出它的每一条边
[输入格式]
第一行三个数n,m,flag，题意如上所示 第2~1+m行，每行三个数，x,y,z，代表从x到y有一条长为z的边
[输出格式]
若flag=1则m行，flag=0则m2行，无向图中边a-b，存储 a -> b和 b -> a两条，所以为m * 2
每行三个数，即该点的编号、所指向点的编号，边的长度，先按第一个数升序排列，再以链式前向星中的顺序输出即可
其实就是i从1到n，再按顺序查找边输出即可, 特殊的，若该点无出边，单独一个空行
[输入输出样例]
输入 #1
5 5 0
1 2 5
1 4 6
2 3 7
3 5 3
3 4 1
输出 #1
1 4 6
1 2 5
2 3 7
2 1 5
3 4 1
3 5 3
3 2 7
4 3 1
4 1 6
5 3 3
输入 #2
4 3 1
1 3 6
3 4 1
2 1 3
输出 #2
1 3 6
2 1 3
3 4 1
说明/提示
对于100%的数据，m<=4000000;l<=1e9;保证图连通
2 相关知识点
1) 结构体
结构体属于用户自定义的数据类型，允许用户存储不同的数据类型
例如：
学生有姓名/年龄/分数，其中，姓名和年龄/分数是不同类型，因此不能使用数组准确存储
创建结构体
创建一个新的学生数据类型：学生包括（姓名，年龄，分数）
struct Student{
//成员列表
//姓名
string name;
//年龄
int age;
//分数
int score;
};
声明结构体类型
Student s1;
结构体赋值
s1.name = "张三";
s1.age = 18;
s1.score = 100;
整体示例参考
#include <bits/stdc++.h>
using namespace std;
/*创建学生数据类型
struct 类型名称 { 成员列表 }
*/
struct Student{
//成员列表
//姓名
string name;
//年龄
int age;
//分数
int score;
}S[10];//定义以Student为类型的数组S
int main(){
Student s1; //声明结构体变量
//给s1属性赋值，通过.访问结构体变量中的属性
s1.name = "张三";
s1.age = 18;
s1.score = 100;
cout << "姓名：" << s1.name << "年龄：" << s1.age << "分数：" << s1.score << endl;
Student s2 = { "李四" , 19 , 80 };//声明结构体变量并赋值
cout << "姓名：" << s1.name << "年龄：" << s1.age << "分数：" << s1.score << endl;
//结构体数组
S[0].name = "王五";
S[0].age = 30;
S[0].score = 98;
cout << "姓名：" << S[0].name << "年龄：" << S[0].age << "分数：" << S[0].score << endl;
return 0;
}
2) 链表
是一种常见的数据结构，它是由一系列节点（Node）组成，每个节点包含两部分：数据域和指针域。数据域用于存储数据，指针域用于存储下一个节点的地址。链表的第一个节点称为头节点（Head），最后一个节点称为尾节点（Tail），尾节点的指针域指向空（NULL）
在结点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的结点。
因为只有一个指针结点，称为单链表
3) 链式前向星
链式前向星就是把数据以链表形式连接在一起,通过起点，把相同起点的边连接在一起，每个点为起点的所有边
3 思路分析
#include<bits/stdc++.h>
using namespace std;
const int N=4000010;
long long n,m,f,cnt,h[N];
/*
h[] 存储对应元素起点的最大下标
例如 边1->3 1->4 1->5 此时h[1]的值为3
e数组 存储所有边，其中这些边相同起点通过链表串连到一起
例如 边1->3 1->4 1->5
上面3条边通过起点1连在一起，5->next为4，5->next为3
*/
struct node{//相同起点为1个链表
int next,w,to;//to边连向的点 w 边的长度 next下一个结点
}e[N];
/*
链式前向星加边
加a到b的边 边权为c
*/
void add(int a,int b,int c){
cnt++;//增加一条边对应数组下标
e[cnt].to=b;//指向b结点
e[cnt].w=c;//边权为c
e[cnt].next=h[a];//下一个结点执向h[a] 指向前一个结点
h[a]=cnt;//h[a]指向当前结点 增加了1条边 ，h[a]加1
}
int main(){
cin>>n>>m>>f;//n个结点 m条边 f有向或无向图
for(int i=1;i<=m;i++){//一次输入m条边
int a,b,c;//从a到b的边 长度为c
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);//加一条从a到b的边，长度为c
if(f==0){//如果f为0说明为无向图，同时增加一条从b到a，长度为c的边
add(b,a,c);
}
}
//输出
for(int i=1;i<=n;i++){//i如果为0说明没有以i为起点的边，如果不为0，h[i]的值则是以i为起点的边数
for(int k=h[i];k;k=e[k].next) {//遍历i为起点的边
printf("%d %d %d\n",i,e[k].to,e[k].w);
}
}
return 0;
}