2026年深入理解noip竞赛中的图论问题

2026年深入理解noip竞赛中的图论问题第一部分：基础概念与简单应用（共3题，每题10分）题目1（10分）：给定一个包含n个节点（编号1～n）和m条边的无向图，请判断该图是否为树。如果是树，请输出“是”；否则输出“否”。假设边用三元组(u,v,w)表示，其中u和v为节点编号，w为边权（若为树问题，可忽略权值）。输入格式：第一行输入两个整数n和m，表示节点数和边数。接下来m行，每行输入三个整数u,v,w，表示一条从u到v的边（无向）。输出格式：一行输出“是”或“否”。示例：输入：44121231341141输出：是题目2（10分）：给定一个包含n个节点和m条边的有向图，请判断该图是否存在负权回路。若存在，输出“是”；否则输出“否”。输入格式：第一行输入两个整数n和m，表示节点数和边数。接下来m行，每行输入三个整数u,v,w，表示一条从u到v的边（有向），w为边权。输出格式：一行输出“是”或“否”。示例：输入：3312-123-131-2输出：是题目3（10分）：给定一个包含n个节点和m条边的无向连通图，请判断该图是否为欧拉图（即是否存在经过所有边恰好一次的回路）。若为欧拉图，输出“是”；否则输出“否”。输入格式：第一行输入两个整数n和m，表示节点数和边数。接下来m行，每行输入两个整数u,v，表示一条边。输出格式：一行输出“是”或“否”。示例：输入：451223344124输出：是第二部分：最短路径问题（共3题，每题15分）题目4（15分）：给定一个包含n个节点和m条边的有向带权图，起点为1，终点为n。请使用Dijkstra算法计算从起点到终点的最短路径长度。若无法到达，输出“-1”。输入格式：第一行输入两个整数n和m，表示节点数和边数。接下来m行，每行输入三个整数u,v,w，表示一条从u到v的边，w为边权。输出格式：一行输出最短路径长度或“-1”。示例：输入：56122136233241347451输出：4题目5（15分）：给定一个包含n个节点和m条边的无向带权图，起点为1，终点为n。请使用Bellman-Ford算法计算从起点到终点的最短路径长度。若存在负权回路且终点可达，输出“无限”；否则输出最短路径长度或“-1”。输入格式：第一行输入两个整数n和m，表示节点数和边数。接下来m行，每行输入三个整数u,v,w，表示一条边，w为边权。输出格式：一行输出最短路径长度、“-1”或“无限”。示例：输入：4412123-134141-3输出：无限题目6（15分）：给定一个包含n个节点和m条边的无向带权图，请使用Floyd-Warshall算法计算所有节点对的最短路径长度。若某对节点不可达，输出“inf”。输入格式：第一行输入一个整数n，表示节点数。接下来m行，每行输入三个整数u,v,w，表示一条边，w为边权。输出格式：输出一个n×n的矩阵，表示所有节点对的最短路径长度。不可达的边用“inf”表示。示例：输入：441222313431410输出：02infinfinf01infinfinf03infinfinf0第三部分：拓扑排序与关键路径（共2题，每题20分）题目7（20分）：给定一个包含n个节点和m条边的有向无环图（DAG），请输出其拓扑排序序列。若该图不是DAG，输出“无解”。输入格式：第一行输入两个整数n和m，表示节点数和边数。接下来m行，每行输入两个整数u,v，表示一条从u到v的边。输出格式：一行输出拓扑排序序列，或“无解”。示例：输入：66121324344546输出：132465题目8（20分）：给定一个包含n个节点和m条边的有向带权图（DAG），每个节点有一个权重（设为pi），每条边的权重为时间（设为tij）。请计算从节点1到所有其他节点的最长路径长度（带权值之和）。若无法到达某节点，输出“inf”。输入格式：第一行输入两个整数n和m，表示节点数和边数。接下来m行，每行输入四个整数u,v,tij,pi，表示一条从u到v的边，tij为时间权，pi为节点v的权重。输出格式：一行输出从节点1到所有其他节点的最长路径长度，用空格分隔。不可达的节点用“inf”表示。示例：输入：441223133424123425输出：365inf第四部分：最小生成树与网络流（共2题，每题25分）题目9（25分）：给定一个包含n个节点和m条边的无向带权图，请使用Kruskal算法计算其最小生成树（MST）的总权值。若图不连通，输出“-1”。输入格式：第一行输入两个整数n和m，表示节点数和边数。接下来m行，每行输入三个整数u,v,w，表示一条边，w为边权。输出格式：一行输出MST的总权值或“-1”。示例：输入：56122133231244355452输出：7题目10（25分）：给定一个包含n个节点和m条边的有向带权图，其中每个节点有一个容量限制。请使用Ford-Fulkerson算法计算从节点1到节点n的最大流。输入格式：第一行输入两个整数n和m，表示节点数和边数。接下来m行，每行输入四个整数u,v,c,f，表示一条从u到v的边，c为容量，f为初始流量（默认为0）。输出格式：一行输出最大流值。示例：输入：451210013502410034502320输出：10答案与解析第一部分：基础概念与简单应用题目1（10分）：输出：是解析：-判断是否为树需满足两个条件：①无向图；②n-1条边且无环。-输入图有4个节点、4条边，正好是n-1（4-1=3），且无向边不构成环（任意两点间只有一条路径），故为树。题目2（10分）：输出：是解析：-使用Bellman-Ford算法检测负权回路：从1出发，更新路径长度。-路径1→2→3→1的权值和为1+(-1)+(-1)=-1，存在负权回路。题目3（10分）：输出：是解析：-判断欧拉图需满足：①无向图；②所有节点度数为偶数。-节点度数：1（2+0），2（2+2），3（2+1），4（2+2），均为偶数，且无向连通，故为欧拉图。第二部分：最短路径问题题目4（15分）：输出：4解析：-Dijkstra算法：1.起点更新：1→2（2）2.2→4（3）3.4→5（4）-最短路径为1→2→4→5，长度为4。题目5（15分）：输出：无限解析：-Bellman-Ford检测负权回路：路径1→2→3→4→1的权值和为1+(-1)+(-1)+(-3)=-4，存在负权回路，终点可达，故无限。题目6（15分）：输出：02infinfinf01infinfinf03infinfinf0解析：-Floyd-Warshall算法：动态更新所有节点对的最短路径。-1→2（2），1→4（10），2→4（5），3→4（6），故1→4的最短路径需绕过3（1→2→4=2+1=3）。第三部分：拓扑排序与关键路径题目7（20分）：输出：132465解析：-拓扑排序：1.入度为0：12.1→2，1→3：2,33.2→4，3→4：44.4→5，4→6：5,6-顺序为1→3→2→4→6→5。题目8（20分）：输出：365inf解析：-计算最长路径：1.1→2（3），1→3（4），1→4（8）2.2→4（4），2→3（5），3→4（7）3.最长路径：1→3→4（4+5=9），1→2→4（3+4=7），1→2→3→4（3+5+7=15），1→4（8）。-终点1可达，2（3），3（6），4（5），无解节点用inf。第四部分：最小生成树与网络流题目9（25分）：输出：7解析：-Kruskal算法：按边权排序（1,2,2,3,4,5），依次选择不形成环的边：1.2-3（1）2.1-2（2）3.4-5（2）4.1-3（3）-总权值1+2+2+3=8，若删除4-5（2），总权值1+2+2+3=8，但需选n-1=4条边，故需调整：-正确选择：2-3（1），1-2（2），4-5（2），1-3（3），总权值1+2+2+3=8。-更优选择：2-3（1），1-2（2），1-3（3），4-5（2），总权值1+2+3+2=8。-最优选