数据结构与算法--贪心、图论篇

图论是数据结构与算法中的一个重要分支，主要研究图的性质、结构及其在计算机科学和其他领域中的应用。图是由一组顶点（或节点）和一组边组成的数学结构。这里我将对图论的基本概念、常见算法以及应用做一个简单介绍。

基本概念

1. 图的定义：

   • 无向图：边没有方向，即边的两个顶点是对等的。
   • 有向图：边有方向，从一个顶点指向另一个顶点。
   • 加权图：边带有权重或成本，表示从一个顶点到另一个顶点的代价。
   • 简单图：没有自环和重边的图。
   • 连通图：在无向图中，任意两个顶点都存在路径相连；在有向图中，如果任意两个顶点之间存在走向的路径则称为强连通图。

2. 图的表示：

   • 邻接矩阵：用一个二维数组表示图，数组中的值表示顶点之间的边的存在性和权重。
   • 邻接表：用链表或数组来表示顶点及其相邻顶点，适合稀疏图。

常见算法

1. 遍历算法：

   • 深度优先搜索（DFS）：从一个顶点出发，尽可能深地搜索下去，直到没有更多的顶点可访问，然后回溯。
   • 广度优先搜索（BFS）：从一个顶点出发，先访问所有相邻的顶点，然后再逐层访问后续顶点。

2. 最短路径算法：

   • Dijkstra算法：适用于带权重的无向图，计算从单个源点到其他所有顶点的最短路径。
   • Bellman-Ford算法：可以处理负权边，适用于没有负权环的图。
   • Floyd-Warshall算法：用于计算任意两个顶点之间的最短路径，适合小型图。

3. 最小生成树：

   • Prim算法：以某个顶点为起点，逐步扩展生成树，选择与当前生成树相连接的最小边。
   • Kruskal算法：通过对所有边按权重排序，逐步添加不形成环的边来构建生成树。

4. 拓扑排序：在有向无环图（DAG）中进行排序，使得每条边的起点排在终点之前。可以使用DFS或Kahn算法实现。

应用

图论在计算机科学和其他领域有广泛的应用，包括但不限于：

• 网络流：如最大流问题、最小费用流问题。
• 社交网络分析：社交图分析人际关系、社区发现。
• 路径规划：如自动驾驶、游戏AI中的最优路径寻找。
• 项目调度：使用拓扑排序和关键路径法进行项目管理。

通过理解图论及其算法，可以帮助解决许多复杂的问题，是算法设计及实现中的一项核心技能。

直接上题：

题目：

T1照常还是送分题无需多言。

​

T2

问题描述

小蓝，一位热爱阅读的青年，常常沉浸在书的世界里。

这天在他逛书店的时候，发现书店里的每一类书籍都有一定的库存数量，而且部分书籍还被贴上了特别的标签。这些标签往往是一些负面评价，比如“印刷存在错误”或者“页码混乱”等等。

小蓝仔细观察了每个书架，并记录下了每类书籍的库存总数以及被贴特别标签的数量。现在，他需要你的帮助来分析这些数据，找出哪一类书籍被贴上特别标签的比例最低，即从该类书籍中随机选择一本时，拿到带有特别标签书籍的概率最小。

输入格式

输入的第一行包含一个整数 𝑁N （1≤𝑁≤1051≤N≤105），表示书籍的类别数量。

接下来的 𝑁N 行，每行包含两个整数 𝑡𝑖ti​ 和 𝑝𝑖pi​ （1≤𝑝𝑖≤𝑡𝑖≤1001≤pi​≤ti​≤100），分别表示第 𝑖i 类书籍的库存总数和被贴特别标签的数量。

输出格式

输出一个整数，表示被贴特别标签比例最低的书籍类别的索引（索引从 11 开始）。如果有多个答案，则输出索引值最小的那个。

样例输入

3
20 5
30 8
40 10

样例输出

1

样例说明

第 11 类书籍和第 33 类书籍被贴上特别标签的比例最低，为 25%25% 。由于 11 索引值更小，因此输出 11 。

送分题，无需多言。

代码实现：

import os
import sys

# 请在此输入您的代码
t=int(input())
ls=1
a_min=0
for i in range(t):
    a,b=map(int,input().split())
    k=b/a
    
    if k<ls: 
        ls=k
        a_min=i+1
print(a_min)

T3

问题描述

“那个帕鲁我已经观察你很久了，我对你是有些失望的，进了这个营地，不是把事情做好就可以的，你需要有体系化思考的能力。”

《幻兽帕鲁》火遍全网，成为了一款现象级游戏。

猫猫作为顶级帕鲁自然是首当其冲搭好了游戏私服，叫上好兄弟开始了愉快私服开荒。

但是这个游戏好玩归好玩，服务器有一堆 bug。比如说众所周知的内存泄漏问题。猫猫很无奈，写了一个脚本去检测服务器的内存占用问题，当超过一定数值就自杀。

但是问题又来了，服务器自杀了之后还要猫猫亲自去手动重启，配置守护进程的诸多方法都不适合。

最终，猫猫决定一分钟监听一次服务器端口是否正常放通。并记录下日志。

具体如下：脚本每隔一分钟监听一次服务端口是否正常，如果服务没有正常运行，则输出 1 并重启服务，否则输出 0。

现在日志形如一段 0101 字符串，00 代表正常运行，11 代表端口关闭。在定时任务监听中遇到端口关闭时会自动重启一次服务器。

现在拿到日志之后，猫猫想知道 [𝑙,𝑟)[l,r) 区间内到底有多少次重启成功。（𝑙l 为起点时刻，𝑟r 为终点时刻。）

注：重启成功为服务从端口关闭状态转换为端口正常运行状态。如果日志的最后一分钟为 11，那么你可以视作最后一分钟为重启失败。

输入格式

第一行输入一个正整数 𝑛n。(1≤𝑛≤2×105)(1≤n≤2×105)

第二行输入一个长度为 𝑛n 的 0101 字符串 𝑆S。(∣𝑆∣=𝑛,𝑠𝑖∈{0,1},1≤𝑖≤𝑛)(∣S∣=n,si​∈{0,1},1≤i≤n)。

第三行输入一个正整数 𝑚m。(1≤𝑚≤2×105)(1≤m≤2×105)

接下来 𝑚m 行，每行输入两个正整数 𝑙,𝑟l,r，表示区间 [𝑙,𝑟)[l,r)。(1≤𝑙<𝑟≤𝑛+1)(1≤l<r≤n+1)。

输出数据

输出 𝑚m 行，表示对于 𝑚m 次查询的结果。

样例输入

5
10110
4
1 2
1 3
2 4
2 5

样例输出 

1
1
0
1

说明

对于第 11 分钟，在重启后第 22 分钟变成 00，说明第 11 分钟重启成功。

对于第 33 分钟，在重启后第 44 分钟依旧是 11，说明第 33 分钟重启失败。

对于第 44 分钟，在重启后第 55 分钟变成 00，说明第 44 分钟重启成功。

思路：首先按照题目输入，如果直接暴力，那只能过8个，所以用到前缀和，根据题意，只要有10字符串，则cnt+=1，所以前缀和遍历，如果有，则+1，否则就是0，最后输出即可 请在此处填写你的解题思路 

代码实现：

import os
import sys

# 请在此输入您的代码
# 读取输入  
n = int(input().strip())  # 读取字符串长度  
s = input().strip()  # 读取01字符串  
m = int(input().strip())  # 读取查询次数  
  
# 初始化前缀和数组，初始值为0  
li = [0] * n  
  
# 遍历字符串，计算每个位置之前的重启次数（即10对的数量）  
for i in range(n - 1):  
    if s[i] == '1' and s[i + 1] == '0':  
        li[i] = 1  
  
# 计算前缀和  
for i in range(1, n):  
    li[i] += li[i - 1]  
  
# 处理查询  
for _ in range(m):  
    l, r = map(int, input().strip().split())  # 读取查询的起始和结束位置  
    l -= 1  # 转换为数组索引（从0开始）  
    r -= 1  # 同样，r也要转换为数组索引，并且是最后一个有效索引  
  
    # 如果l为0，则直接从0开始计数到r-1  
    # 否则，计算li[r-1] - li[l-1]，即[l, r)区间内的重启次数  
    if l == r:
        print(0)  # 注意这里可能会出现l == r的情况，因为左闭右开。
    elif l == 0:  
        print(li[r - 1])  
    else:  
        print(li[r - 1] - li[l - 1])

​

​